Rumah >masalah biasa >fifo是什么页面置换算法
fifo是指先进先出页面置换算法,每次置换最先调入内存的页面,即将内存中等待时间最长的页面进行置换。优点:实现起来比较简单,可以不需要硬件的支持,因而不需要增加系统的成本。
本教程操作环境:windows10系统、Dell G3电脑。
fifo(先进先出页面置换算法)
基本思想:优先淘汰最早进入内存的页面,亦即在内存中驻留时间最久的页面。
该算法实现简单,只需把调入内存的页面根据先后次序链接成队列,设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应,因为在进程中,有的页面经常被访问。
实现过程:
假定系统为某进程分配了三个物理块,并考虑有以下页面号引用串:7, 0, 1, 2, 0, 3, 0,4,2,3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1。釆用FIFO算法进行页面置换,进程访问页面2时,把最早进入内存的页面7换出。然后访问页面3时,再把2, 0, 1中最先进入内存的页换出。由下图可以看出,利用FIFO算法时进行了12次页面置换。
访问页面 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
物理块1 | 7 | 7 | 7 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 | 7 | 7 | 7 | |||||
物理块2 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | 1 | 1 | 0 | 0 | ||||||
物理块3 | 1 | 1 | 1 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | |||||||
缺页否 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ |
缺点:FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象,这是由Belady于1969年发现,故称为Belady异常,如下图所示。只有FIFO算法可能出现Belady异常,而LRU和OPT算法永远不会出现Belady异常。
更多相关知识,请访问常见问题栏目!
Atas ialah kandungan terperinci fifo是什么页面置换算法. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!