采用fifo页面置换算法是

⑴ 页面置换算法有哪些

页面置换算法包括先进先出（FIFO）、最近最久未使用（LRU）、最不常用（LFU）、时钟（Clock）以及理想（OPT）算法。
1. 先进先出（FIFO）算法
该算法的基本原则是先进入内存的页面先被置换。当内存空间不足时，系统会选择最早进入内存的页面进行置换。FIFO算法的优势在于实现简单，但其缺点在于未能考虑页面的实际使用频率和重要性，可能导致不必要的性能损耗。
2. 最近最久未使用（LRU）算法
LRU算法依据页面的历史访问记录来进行页面置换。它倾向于将最长时间未被访问的页面置换出内存。为了有效地追踪页面访问顺序，LRU算法通常需要使用特殊的数据结构，如链表或栈。尽管LRU算法在理论上较为合理，但其实现复杂度较高，且需要额外的存储空间来维护访问顺序。
3. 最不常用（LFU）算法
LFU算法是基于页面访问频率的置换策略。它认为访问频率低的页面在未来也较少会被访问，因此将这些页面置换出内存。LFU算法需要跟踪每个页面的访问频率，并进行相应的排序。然而，LFU算法可能会导致一些频繁访问的页面被过早置换，影响系统性能。
4. 时钟（Clock）算法
Clock算法是基于FIFO的一种改进。它使用一个时钟指针来遍历页面队列，并根据特定的标记位（如访问位或修改位）来决定置换页面。当新页面需要加载时，时钟指针继续移动，直到找到一个标记位为0的页面进行置换。Clock算法的优势在于其实现相对简单且效率较高。
5. 理想（OPT）算法
理想算法是一个理论上的最优页面置换算法，它能够准确预测未来的页面访问模式，并据此选择最长时间内不会被访问的页面进行置换。然而，由于实际中无法准确预测访问模式，OPT算法在现实中无法完美实现。

⑵ 页面置换算法常见的置换算法

页面置换算法在计算机内存管理中扮演重要角色，用于解决内存与处理器之间的数据交换问题。其中，不同算法各有其特点与适用场景。

最佳置换算法（OPT）旨在选择未来永不访问或最久不访问的页面淘汰，以此降低缺页率，实现内存资源的高效利用。

先进先出置换算法（FIFO）遵循“先入先出”原则，淘汰最早进入内存的页面。该算法简单直观，但可能因预测不准确而产生较多缺页现象。

最近最久未使用（LRU）算法基于页面的访问历史，淘汰最近最久未访问的页面，以确保频繁访问的页面得到优先访问机会。

Clock置换算法（LRU算法的近似实现）通过为每帧关联使用位，动态模拟LRU算法的淘汰策略，实现对最近未使用的页面的高效淘汰。

最少使用（LFU）置换算法关注页面的访问频率，淘汰访问次数最少的页面，旨在平衡页面访问频率与内存使用效率。

工作集算法考虑程序运行时的页面使用情况，通过工作集的大小预测页面需求，实现更合理的页面置换。

工作集时钟算法结合Clock置换算法与工作集概念，优化内存管理策略，提升算法效能。

老化算法（类似LRU的有效算法）通过跟踪页面的访问情况，对页面进行“老化”处理，淘汰访问频率较低的页面，以优化内存使用。

NRU（最近未使用）算法追踪页面的使用情况，优先淘汰长时间未被访问的页面，减少缺页现象。

第二次机会算法在页面置换策略中引入二次淘汰机会，对被淘汰页面进行评估，若发现有较高访问频率，可将其重新加入内存，减少因错误预测带来的缺页成本。

在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法

⑶ fifo算法是什么

FIFO（First Input First Output），即先进先出队列。可以类比 我们在饭堂排队打饭，先排到队伍的最后，等待前面的人一个个打完饭再轮到下一个。这就是一种先进先出机制，先排队的人先行打饭离开。

FIFO（先进先出页面置换算法）：看到先进先出，我们想到的数据结构就是队列当分配的内存物理块数量为3时。

6，7，5先进入内存，那么出来的顺序就是5，7，6 缺页次数为3次。

2调入内存，6调出内存，那么顺序就是2，5，7 缺页次数为4次。

6调入内存，7调出内存，那么顺序就是6，2，5 缺页次数为5次。

7调入内存，5调出内存，那么顺序就是7，6，2 缺页次数为6次。

3调入内存，2调出内存，那么顺序就是3，7，6 缺页次数为7次。

6调入内存，已经存在，不需要调入。

7调入内存，已经存在，不需要调入。

5调入内存，6调出内存，那么顺序就是5，3，7 缺页次数为8次。

2调入内存，7调出内存，那么顺序就是2，5，3 缺页次数为9次。

3调入内存，已经存在，不需要调入。

⑷ 页面置换算法的常见的置换算法

最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。
这种算法只是在按线性顺序访问地址空间 时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。
FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。
FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在之前一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（Least Recently Used，LRU）。
LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。
LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需要实际硬件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：
1.计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一个页面时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的“时间”。在置换页面时，选择该时间值最小的页面。这样做， 不仅要查页表，而且当页表改变时（因CPU调度）要 维护这个页表中的时间，还要考虑到时钟值溢出的问题。
2.栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，但需要置换哪个页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。
因实现LRU算法必须有大量硬件支持，还需要一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。
一种LRU近似算法是最近未使用算法（Not Recently Used，NUR）。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在之前最近一段时间里它未被访问过。
4）Clock置换算法（LRU算法的近似实现）
5）最少使用（LFU）置换算法
在采用最少使用置换算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在之前时期使用最少的页面作为淘汰页。由于存储器具有较高的访问速度，例如100 ns，在1 ms时间内可能对某页面连续访 问成千上万次，因此，通常不能直接利用计数器来记录某页被访问的次数，而是采用移位寄存器方式。每次访问某页时，便将该移位寄存器的最高位置1，再每隔一定时间(例如100 ns)右移一次。这样，在最近一段时间使用最少的页面将是∑Ri最小的页。
LFU置换算法的页面访问图与LRU置换算法的访问图完全相同；或者说，利用这样一套硬件既可实现LRU算法，又可实现LFU算法。应该指出，LFU算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况，因此，访问一次和访问10 000次是等效的。
6）工作集算法
7）工作集时钟算法
8）老化算法（非常类似LRU的有效算法）
9）NRU(最近未使用）算法
10）第二次机会算法
第二次机会算法的基本思想是与FIFO相同的，但是有所改进，避免把经常使用的页面置换出去。当选择置换页面时，检查它的访问位。如果是 0，就淘汰这页；如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前时间。如果该页在此期间被访问过，则访问位置1。这样给了第二次机会的页面将不被淘汰，直至所有其他页面被淘汰过（或者也给了第二次机会）。因此，如果一个页面经常使用，它的访问位总保持为1，它就从来不会被淘汰出去。
第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个 存储块时，指针就前进，直至找到访问位是0的页。随着指针的前进，把访问位就清为0。在最坏的情况下，所有的访问位都是1，指针要通过整个队列一周，每个页都给第二次机会。这时就退化成FIFO算法了。