1.0 Topics For the Week
1.1 Understand policies for free space management.- Given that main memory holds some subset of all the pages in the system, it can rightly be viewed as a cache for virtual memory pages in the system. Thus, our goal in picking a replacement policy for this cache is to minimize the number of cache misses, i.e., to minimize the number of times that we have to fetch a page from disk. Alternately, one can view our goal as maximizing the number of cache hits, i.e., the number of times a page that is accessed is found in memory.
-
Knowing the number of cache hits and misses let us calculate the average memory access time (AMAT) for a program (a metric computer architects compute for hardware caches [HP06]). Specifically, given these values, we can compute the AMAT of a program as follows: AMAT = TM +(PMiss ·TD). The optimal replacement policy leads to the fewest number of misses overall.
- FIFO
- Random
- LRU
- FIFO - Many early systems avoided the complexity of trying to approach optimal and employed very simple replacement policies. For example, some systems used FIFO (first-in, first-out) replacement, where pages were simply placed in a queue when they enter the system; when a replacement occurs, the page on the tail of the queue (the “first-in” page) is evicted. FIFO has one great strength: it is quite simple to implement.
- Comparing FIFO to optimal, FIFO does notably worse: a 36.4% hit
rate (or 57.1% excluding compulsory misses). FIFO simply can’t deter-
mine the importance of blocks: even though page 0 had been accessed
a number of times, FIFO still kicks it out, simply because it was the first
one brought into memory.
-
In general, you would expect the cache hit rate to increase (get better) when the cache gets larger. But in this case, with FIFO, it gets worse! Cal- culate the hits and misses yourself and see. This odd behavior is generally referred to as Belady’s Anomaly (to the chagrin of his co-authors).FIFO and Random (among others) clearly do not obey the stack property, for algorithms with this property, a cache of size N + 1 naturally includes the contents of a cache of size N . Thus, when increasing the cache size, hit rate will either stay the same or improve and thus are susceptible to anomalous behavior.
- Random - Another similar replacement policy is Random, which simply picks a random page to replace under memory pressure. Random has properties similar to FIFO; it is simple to implement, but it doesn’t really try to be too intelligent in picking which blocks to evict.
- LFU - The Least-Frequently-Used (LFU) policy replaces the least-frequently-used page when an eviction must take place
- LRU - The Least-Recently- Used (LRU) policy replaces the least-recently-used page.
- MFU - Most- Frequently-Used (MFU)
- MRU - Most recently used (MRU)
-
Paging, as we will see, has a number of advantages over our previous approaches. Probably the most important improvement will be flexibility: with a fully-developed paging approach, the system will be able to support the abstraction of an address space effectively, regardless of how a process uses the address space; we won’t, for example, make assumptions about the direction the heap and stack grow and how they are used.
-
Another advantage is the simplicity of free-space management that paging affords. For example, when the OS wishes to place our tiny 64-byte address space into our eight-page physical memory, it simply finds four free pages; perhaps the OS keeps a free list of all free pages for this, and just grabs the first four free pages off of this list. In the example, the OS has placed virtual page 0 of the address space (AS) in physical frame 3, virtual page 1 of the AS in physical frame 7, page 2 in frame 5, and page 3 in frame 2. Page frames 1, 4, and 6 are currently free.
-
With page tables in memory, we already know that they might be too big. As it turns out, they can slow things down too. However, implementing paging support without care will lead to a slower machine (with many extra memory accesses to access the page table) as well as memory waste (with memory filled with page tables instead of useful application data).
- To translate this virtual address that the process generated, we have to first split it into two components: the virtual page number (VPN), and the offset within the page. For this example, because the virtual address space of the process is 64 bytes, we need 6 bits total for our virtual address (26 = 64).
-
The page size is 16 bytes in a 64-byte address space; thus we need to be able to select 4 pages, and the top 2 bits of the address do just that. Thus, we have a 2-bit virtual page number (VPN). The remaining bits tell us which byte of the page we are interested in, 4 bits in this case; we call this the offset.
-
When a process generates a virtual address, the OS and hardware must combine to translate it into a meaningful physical address. For example, let us assume the load above was to virtual address 21. Turning “21” into binary form, we get “010101”, and thus we can examine this virtual address and see how it breaks down into a virtual page number (VPN) and offset:
-
Thus, the virtual address “21” is on the 5th (“0101”th) byte of virtual page “01” (or 1). With our virtual page number, we can now index our page table and find which physical frame virtual page 1 resides within. In the page table above the physical frame number (PFN) (also sometimes called the physical page number or PPN) is 7 (binary 111). Thus, we can translate this virtual address by replacing the VPN with the PFN and then issue the load to physical memory (Figure 18.3).
-
Note the offset stays the same (i.e., it is not translated), because the offset just tells us which byte within the page we want. Our final physical address is 1110101 (117 in decimal), and is exactly where we want our load to fetch data from (Figure 18.2, page 2)
-
There are two types of locality that programs tend to exhibit. The first is known as spatial locality, which states that if a page P is accessed, it is likely the pages around it (say P − 1 or P + 1) will also likely be accessed. The second is temporal locality, which states that pages that have been accessed in the near past are likely to be accessed again in the near future. The assumption of the presence of these types of locality plays a large role in the caching hierarchies of hardware systems, which deploy many levels of instruction, data, and address-translation caching to help programs run fast when such locality exists.
Of course, the principle of locality, as it is often called, is no hard-and-fast rule that all programs must obey. Indeed, some programs access memory (or disk) in rather random fashion and don’t exhibit much or any locality in their access streams. Thus, while locality is a good thing to keep in mind while designing caches of any kind (hardware or software), it does not guarantee success. Rather, it is a heuristic that often proves useful in the design of computer systems.
- Knowing the number of cache hits and misses let us calculate the average memory access time (AMAT) for a program (a metric computer
architects compute for hardware caches [HP06]). Specifically, given these
values, we can compute the AMAT of a program as follows: AMAT = TM +(PMiss ·TD).
Paging is a non-contiguous memory allocation technique in which we convert the entire process in to equal sized pages. Each page further consists of a fixed number of words (if it is word addressable). Page table is a data structure that performs the mapping of page number to the frame number.
Multilevel paging is a paging scheme where there exists a hierarchy of page tables.
The need for multilevel paging arises when the size of page table is greater than the frame size. As a result, the page table can not be stored in a single frame in main memory.
In multilevel paging, the page table having size greater than the frame size is divided into several parts. The size of each part is same as frame size except possibly the last part. The pages of page table are then stored in different frames of the main memory. To keep track of the frames storing the pages of the divided page table, another page table is maintained. As a result, the hierarchy of page tables get generated. Multilevel paging is done till the level is reached where the entire page table can be stored in a single frame.
Multilevel Paging is a paging scheme which consist of two or more levels of page tables in a hierarchical manner. It is also known as hierarchical paging. The entries of the level 1 page table are pointers to a level 2 page table and entries of the level 2 page tables are pointers to a level 3 page table and so on. The entries of the last level page table are stores actual frame information. Level 1 contain single page table and address of that table is stored in PTBR (Page Table Base Register).
In multilevel paging whatever may be levels of paging all the page tables will be stored in main memory. So it requires more than one memory access to get the physical address of page frame. One access for each level needed. Each page table entry except the last level page table entry contains base address of the next level page table.
Reference to actual page frame:
- Reference to PTE in level 1 page table = PTBR value + Level 1 offset present in virtual address.
- Reference to PTE in level 2 page table = Base address (present in Level 1 PTE) + Level 2 offset (present in VA).
- Reference to PTE in level 3 page table= Base address (present in Level 2 PTE) + Level 3 offset (present in VA).
- Actual page frame address = PTE (present in level 3).
Disadvantage: Extra memory references to access address translation tables can slow programs down by a factor of two or more. Use translation look aside buffer (TLB) to speed up address translation by storing page table entries.
Swapping is a process of swapping a process temporarily to a secondary memory from main memory which is fast as compared to secondary memory.
- But as RAM is of less size so the process that is inactive is transferred to secondary memory.
The main part of swapping is transferred time and the total time directly proportional to the amount of memory swapped.
1.11 Characterize policies in terms of average memory time and cache hit rates.
- See above.
No comments:
Post a Comment