:PROPERTIES: :ID: 02c9d7e1-e6cb-4492-8116-2a8b203f8513 :mtime: 20240314095224 :ctime: 20240314095223 :END: #+title: FIFO Page replacement #+filetags: :public:operatingsystems:project: * FIFO ** Definition of FIFO - The simplest page-replacement algorithm is a first-in, first-out (FIFO) algorithm. - A FIFO replacement algorithm associates with each page the time when that page was brought into memory. - When a page must be replaced, the oldest page is chosen. - Notice that it is not strictly necessary to record the time when a page is brought in. - We can create a FIFO queue to hold all pages in memory. We replace the page at the head of the queue. When a page is brought into memory, we insert it at the tail of the queue. ** Performance of FIFO - The FIFO page-replacement algorithm is easy to understand and program. - However, its performance is not always good. - On the one hand, the page replaced may be an initialization module that was used a long time ago and is no longer needed. On the other hand, it could contain a heavily used variable that was initialized early and is in constant use. - Notice that, even if we select for replacement a page that is in active use, everything still works correctly. - After we replace an active page with a new one, a fault occurs almost immediately to retrieve the active page. Some other page must be replaced to bring the active page back into memory. Thus, a bad replacement choice increases the page-fault rate and slows process execution. It does not, however, cause incorrect execution. To illustrate the problems that are possible with a FIFO page-replacement algorithm, we consider the following reference string: ** Belady's Anomaly For some page-replacement algorithms, the [[id:05c5d285-13cb-420b-98ba-1370be5c6c15][page-fault]] rate may increase as the number of allocated frames increases. We would expect that giving more memory to a process would improve its performance. In some early research, investigators noticed that this assumption was not always true. [[id:040b0520-13a0-49dc-80f1-f27fc21ee8ab][Belady’s anomaly]] was discovered as a result.