(28.218.81608.81609.81613.222.81848.81884.82101)
1. FIFO The most simple page replacement algorithm is first in first out (FIFO) method. The essence of this algorithm, always choose the longest stay in memory (i.e. the oldest) page replacement, first into the memory page, first out of memory. The reason is: transferred to the memory of the first page, the possibility of no longer being used into memory than just the possibility of large. Create a FIFO queue that holds all the pages in memory. The replacement page is always on the queue header. When a page is put into memory, put it on the tail. This algorithm is only in linear order to access the address space is ideal, otherwise the efficiency is not high. Because of the frequently visited pages, often stays in memory most for a long time, the “old” because they had to be replaced out. Another drawback of FIFO is that it has an unusual phenomenon that, in the case of increased memory blocks, page breaks are increased. Of course, the page that leads to this anomaly is actually rare. 2. OPT Optimal permutation (Optimal Replacement) is an algorithm proposed in theory. Its essence is: when transferred to a new page and a page replacement must be old, the old page selected should be the future is no longer in use, or in the near future to be accessed. This page replacement algorithm, to ensure the minimum page missing rate. But the implementation of the optimal page replacement algorithm is difficult, because it requires people to know in advance the entire process of running a process page to the full situation. However, this algorithm can be used to measure the merits of other algorithms such as simulation analysis or theoretical analysis. 3. LRU FIFO algorithm and the main difference between the OPT algorithm is that the FIFO algorithm uses the length of time after the page into memory as a replacement basis, and OPT algorithm is based on the future use of the page time. If you use the nearest past as a near future approximation, you can replace the pages that have not been used for the longest time in the past. Its essence is that when you need to replace a page, select the most recent period of time has not been used to replace the page. This algorithm is called the longest unused algorithm (Least Recently Used, LRU). The LRU algorithm is related to the last time each page is used. When a page must be replaced, the LRU algorithm selects the longest used page in the past time. LRU algorithm is often used in the page replacement algorithm, and is considered quite good, but there are problems with how to achieve it. LRU algorithm requires actual hardware support. The problem is how to determine the order of last use time, there are two possible ways: (1) counter. The simplest case is to make each page table item correspond to a usage time field and add a logical clock or counter to the CPU. Each storage access, the clock is plus 1. Whenever a page is accessed, the contents of the clock register are copied to the use time field of the corresponding page table entry. So that we can always retain the last time each page access”. In the replacement page, select the minimum value of the page. To do so, not only to check the page table, and when the page table changes (due to CPU scheduling) to maintain the time in this page table, but also take into account the issue of the clock value overflow. (2) stack. Save page number with one stack. Whenever you access a page, remove it from the stack and place it on the top of the stack. As a result, the stack top always put the most used page, while the bottom of the stack is currently the least used page. Due to the removal of a stack from the middle, so use a two-way Chain with head and tail pointer together. In the worst case, removing a page and placing it on the top of the stack requires changing the 6 pointer. Each modification must have overhead, but need to replace which page can be directly obtained, do not need to find, because the tail pointer to the bottom of the stack, which has been replaced page. Due to the realization of LRU algorithm must have a lot of hardware support, but also need some software overhead. So the actual implementation is a simple and effective LRU approximation algorithm. A LRU approximation algorithm is the recently unused algorithm (Not Recently Used, NUR). It adds a reference bit to each table item in the storage partition table, which the operating system periodically sets to 0. When a page is accessed, the location is 1 by hardware. After a period of time, these pages can be checked by checking which pages are used and which pages have not been used since the last 0. You can eliminate this page by 0 because it hasn’t been visited in recent times. 4. SCR The basic idea of the second chance algorithm is the same as FIFO, but improved, to avoid the often used page replacement. When selecting a replacement page, check its access bit. If it is 0, eliminate this page; if the access bit is 1, give it a second chance and select the next FIFO page. When a page gets a second chance, its access bit is cleared to 0 and its arrival time is set to the current time. If the page is accessed during this time, the access location 1. This gives the second chance the page will not be eliminated until all other pages have been eliminated (or given a second chance). Therefore, if a page is often used, its access bit remains at 1, which is never eliminated. Second chance algorithm can be regarded as an annular queue. Use a pointer to indicate which page is to be eliminated. When a memory block is needed, the pointer advances until the access bit is found 0. As the pointer advances, the access bit is cleared to 0. In the worst case, all the access bits are 1, the pointer through the entire queue a week, each page gives a second chance. Then degenerate into FIFO algorithm.
group status
👤 group joined: 0 ⏳ group pending: 0 🚫 group blocked: 0
> Computer and Education > courses > university courses > undergraduate courses > Operating System > CLASS (2016-2017-1)-62903-06102-1 > > >
(28.218.81608.81609.81613.222.81848.81884.82101)