CGS3269 Lecture 8 Memory PDF

6.5 Virtual Memory Cache memory enhances performance by providing faster memory access speed. Virtual memory enhances performance by providing greater memory capacity, without the expense of adding main memory. Instead, a portion of a disk drive serves as an extension of main memory....

6.5 Virtual Memory Cache memory enhances performance by providing faster memory access speed. Virtual memory enhances performance by providing greater memory capacity, without the expense of adding main memory. Instead, a portion of a disk drive serves as an extension of main memory. If a system uses paging, virtual memory partitions main memory into individually managed page frames, that are written (or paged) to disk when they are not immediately needed. 1  6.5 Virtual Memory A physical address is the actual memory address of physical memory. Programs create virtual addresses that are mapped to physical addresses by the memory manager. Page faults occur when a logical address requires that a page be brought in from disk. Memory fragmentation occurs when the paging process results in the creation of small, unusable clusters of memory addresses. 2  6.5 Virtual Memory Main memory and virtual memory are divided into equal sized pages. The entire address space required by a process need not be in memory at once. Some parts can be on disk, while others are in main memory. Further, the pages allocated to a process do not need to be stored contiguously-- either on disk or in memory. In this way, only the needed pages are in memory at any time, the unnecessary pages are in slower disk storage. 3  6.5 Virtual Memory Information concerning the location of each page, whether on disk or in memory, is maintained in a data structure called a page table (shown below). There is one page table for each active process. 4  6.5 Virtual Memory When a process generates a virtual address, the operating system translates it into a physical memory address. To accomplish this, the virtual address is divided into two fields: A page field, and an offset field. The page field determines the page location of the address, and the offset indicates the location of the address within the page. The logical page number is translated into a physical page frame through a lookup in the page table. 5  6.5 Virtual Memory If the valid bit is zero in the page table entry for the logical address, this means that the page is not in memory and must be fetched from disk. – This is a page fault. – If necessary, a page is evicted from memory and is replaced by the page retrieved from disk, and the valid bit is set to 1. If the valid bit is 1, the virtual page number is replaced by the physical frame number. The data is then accessed by adding the offset to the physical frame number. 6  6.5 Virtual Memory As an example, suppose a system has a virtual address space of 8K and a physical address space of 4K, and the system uses byte addressing. – We have 213/210 = 23 virtual pages. A virtual address has 13 bits (8K = 213) with 3 bits for the page field and 10 for the offset, because the page size is 1024. A physical memory address requires 12 bits, the first two bits for the page frame and the trailing 10 bits the offset. 7  6.5 Virtual Memory Suppose we have the page table shown below. What happens when CPU generates address 5459 10 = 10101010100112 = 1553 16? 8  6.5 Virtual Memory What happens when CPU generates address 5459 10 = 10101010100112 = 1553 16? The high-order 3 bits of the virtual address, 101 (510), provide the page number in the page table. 9  6.5 Virtual Memory The address 10101010100112 is converted to physical address 0101010100112 = 136316 because the page field 101 is replaced by frame number 01 through a lookup in the page table. 10  6.5 Virtual Memory What happens when the CPU generates address 10000000001002? 11  6.5 Virtual Memory We said earlier that effective access time (EAT) takes all levels of memory into consideration. Thus, virtual memory is also a factor in the calculation, and we also have to consider page table access time. Suppose a main memory access takes 200ns, the page fault rate is 1%, and it takes 10ms to load a page from disk. We have: EAT = 0.99(200ns + 200ns) 0.01(10ms) = 100, 396ns. 12  6.5 Virtual Memory Even if we had no page faults, the EAT would be 400ns because memory is always read twice: First to access the page table, and second to load the page from memory. Because page tables are read constantly, it makes sense to keep them in a special cache called a translation look-aside buffer (TLB). TLBs are a special associative cache that stores the mapping of virtual pages to physical pages. The next slide shows address lookup steps when a TLB is involved. 13  TLB lookup process 1. Extract the page number from the virtual address. 2. Extract the offset from the virtual address. 3. Search for the virtual page number in the TLB. 4. If the (virtual page #, page frame #) pair is found in the TLB, add the offset to the physical frame number and access the memory location. 5. If there is a TLB miss, go to the page table to get the necessary frame number. If the page is in memory, use the corresponding frame number and add the offset to yield the physical address. 6. If the page is not in main memory, generate a page fault and restart the access when the page fault is complete. 14 Effective Memory Access (EMA) RAM CPU TLB PT 1 2 miss RAM access = 200 ns hit Ram-access TLB access = 0 ns 1 EMA = %hit * Ram-access + %miss * 2 * Ram-access ( 0% to 100%) EMA = hit * Ram-access + miss * 2 * Ram-access ( 0 to 1) EMA =.95 * 200 +.05 * 200 * 2 = 210 ns EMA =.9 * 200 +.1 * 200 * 2 = 220 ns EMA =.97 * 200 +.03 * 200 * 2 = 206 ns EMA =.99 * 200 +.01 * 200 * 2 = 202 ns EMA =.70 * 200 +.3 * 200 * 2 = 260 ns 15 Effective Memory Access (EMA) RAM CPU TLB PT 1 2 miss RAM access = 200 ns TLB access = 2 ns hit Ram-access 1 EMA = hit * Ram-access + miss * 2 * Ram-access + TLB access EMA =.95 * 200 +.05 * 200 * 2 + 2ns = 212 ns EMA =.9 * 200 +.1 * 200 * 2 + 2ns = 222 ns EMA =.97 * 200 +.03 * 200 * 2 + 2ns = 208 ns miss = 1 - hit EMA =.99 * 200 +.01 * 200 * 2 + 2ns = 204 ns EMA =.70 * 200 +.3 * 200 * 2 + 2ns = 262 ns 16 Putting it all together: The TLB, Page Table, 6.5 Virtual Memory and Main Memory 17  6.5 Virtual Memory Another approach to virtual memory is the use of segmentation. Instead of dividing memory into equal-sized pages, virtual address space is divided into variable-length segments, often under the control of the programmer. A segment is located through its entry in a segment table, which contains the segment’s memory location and a bounds limit that indicates its size. After a page fault, the operating system searches for a location in memory large enough to hold the segment that is retrieved from disk. 18  6.5 Virtual Memory Both paging and segmentation can cause fragmentation. Paging is subject to internal fragmentation because a process may not need the entire range of addresses contained within the page. Thus, there may be many pages containing unused fragments of memory. Segmentation is subject to external fragmentation, which occurs when contiguous chunks of memory become broken up as segments are allocated and deallocated over time. The next slides illustrate internal and external fragmentation. 19  6.5 Virtual Memory Consider a small computer having 32K of memory. The 32K memory is divided into 8 page frames of 4K each. A schematic of this configuration is shown at the right. The numbers at the right are memory frame addresses. 20  6.5 Virtual Memory Suppose there are four processes waiting to be loaded into the system with memory requirements as shown in the table. We observe that these processes require 31K of memory. 21  6.5 Virtual Memory When the first three processes are loaded, memory looks like this: All of the frames are occupied by three of the processes. 22  6.5 Virtual Memory Despite the fact that there are enough free bytes in memory to load the fourth process, P4 has to wait for one of the other three to terminate, because there are no unallocated frames. This is an example of internal fragmentation. 23  6.5 Virtual Memory Suppose that instead of frames, our 32K system uses segmentation. The memory segments of two processes is shown in the table at the right. The segments can be allocated anywhere in memory. 24  6.5 Virtual Memory All of the segments of P1 and one of the segments of P2 are loaded as shown at the right. Segment S2 of process P2 requires 11K of memory, and there is only 1K free, so it waits. 25  6.5 Virtual Memory Eventually, Segment 2 of Process 1 is no longer needed, so it is unloaded giving 11K of free memory. But Segment 2 of Process 2 cannot be loaded because the free memory is not contiguous. 26  6.5 Virtual Memory Over time, the problem gets worse, resulting in small unusable blocks scattered throughout physical memory. This is an example of external fragmentation. Eventually, this memory is recovered through compaction, and the process starts over. 27  6.5 Virtual Memory Large page tables are cumbersome and slow, but with its uniform memory mapping, page operations are fast. Segmentation allows fast access to the segment table, but segment loading is labor-intensive. Paging and segmentation can be combined to take advantage of the best features of both by assigning fixed-size pages within variable-sized segments. Each segment has a page table. This means that a memory address will have three fields, one for the segment, another for the page, and a third for the offset. 28  6.6 A Real-World Example The Pentium architecture supports both paging and segmentation, and they can be used in various combinations including unpaged unsegmented, segmented unpaged, and unsegmented paged. The processor supports two levels of cache (L1 and L2), both having a block size of 32 bytes. The L1 cache is next to the processor, and the L2 cache sits between the processor and memory. The L1 cache is in two parts: and instruction cache (I- cache) and a data cache (D-cache). The next slide shows this organization schematically. 29  6.6 A Real-World Example 30  Chapter 6 Conclusion Computer memory is organized in a hierarchy, with the smallest, fastest memory at the top and the largest, slowest memory at the bottom. Cache memory gives faster access to main memory, while virtual memory uses disk storage to give the illusion of having a large main memory. Cache maps blocks of main memory to blocks of cache memory. Virtual memory maps page frames to virtual pages. There are three general types of cache: Direct mapped, fully associative and set associative. 31  Chapter 6 Conclusion With fully associative and set associative cache, as well as with virtual memory, replacement policies must be established. Replacement policies include LRU, FIFO, or LFU. These policies must also take into account what to do with dirty blocks. All virtual memory must deal with fragmentation, internal for paged memory, external for segmented memory. 32