页面置换算法实现

⑴ 先进先出页面置换算法的实现过程

假定系统为某进程分配了三个物理块，并考虑有以下页面号引用串：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次页面置换。 访问页面70120304230321201701物理块1777222444000777物理块200033322211100物理块31110003332221缺页否√√√√√√√√√√√√√√√

⑵ 页面置换算法的实验

#include <stdio.h>
#define PROCESS_NAME_LEN 32 /*进程名称的最大长度*/
#define MIN_SLICE 10 /*最小碎片的大小*/
#define DEFAULT_MEM_SIZE 1024 /*默认内存的大小*/
#define DEFAULT_MEM_START 0 /*默认内存的起始位置*/

/* 内存分配算法 */
#define MA_FF 1
#define MA_BF 2
#define MA_WF 3

int mem_size=DEFAULT_MEM_SIZE; /*内存大小*/
int ma_algorithm = MA_FF; /*当前分配算法*/
static int pid = 0; /*初始pid*/
int flag = 0; /*设置内存大小标志*/

struct free_block_type
{
int size;
int start_addr;
struct free_block_type *next;
};
struct free_block_type *free_block;

struct allocated_block
{
int pid;
int size;
int start_addr;
char process_name[PROCESS_NAME_LEN];
struct allocated_block *next;
};
struct allocated_block *allocated_block_head;

/*初始化空闲块，默认为一块，可以指定大小及起始地址*/
struct free_block_type* init_free_block(int mem_size)
{

struct free_block_type *fb;

fb=(struct free_block_type *)malloc(sizeof(struct free_block_type));
if(fb==NULL)
{
printf("No mem\n");
return NULL;
}
fb->size = mem_size;
fb->start_addr = DEFAULT_MEM_START;
fb->next = NULL;
return fb;
}

void display_menu()
{
printf("\n");
printf("1 - Set memory size (default=%d)\n", DEFAULT_MEM_SIZE);
printf("2 - Select memory allocation algorithm\n");
printf("3 - New process \n");
printf("4 - Terminate a process \n");
printf("5 - Display memory usage \n");
printf("0 - Exit\n");
}

/*设置内存的大小*/
int set_mem_size()
{
int size;
if(flag!=0)
{ /*防止重复设置*/
printf("Cannot set memory size again\n");
return 0;
}
printf("Total memory size =");
scanf("%d", &size);
if(size>0)
{
mem_size = size;
free_block->size = mem_size;
}
flag=1;
return 1;
}
/*Best-fit使用最小的能够放下将要存放数据的块，First-first使用第一个能够放下将要存放数据的块，Worst-fit使用最大的能够放下将要存放数据的块。*/
/* 设置当前的分配算法 */
/*分区分配算法(Partitioning Placement Algorithm)
*/
void set_algorithm()
{
int algorithm;
printf("\t1 - First Fit\n");/*首次适应算法(FF)：。 */
printf("\t2 - Best Fit\n");/*最佳适应算法(BF)： */

printf("\t3 - Worst Fit\n");
scanf("%d", &algorithm);
if(algorithm>=1 && algorithm <=3) ma_algorithm=algorithm;
/*按指定算法重新排列空闲区链表*/
rearrange(ma_algorithm);
}

void swap(int* data_1,int* data_2)
{
int temp;
temp=*data_1;
*data_1=*data_2;
*data_2=temp;
}

void rearrange_FF()
{
struct free_block_type *tmp, *work;
printf("Rearrange free blocks for FF \n");
tmp = free_block;
while(tmp!=NULL)
{
work = tmp->next;
while(work!=NULL)
{
if( work->start_addr < tmp->start_addr)
{ /*地址递增*/
swap(&work->start_addr, &tmp->start_addr);
swap(&work->size, &tmp->size);
}
else
{
work=work->next;
}
}
tmp=tmp->next;
}
}
/*按BF算法重新整理内存空闲块链表(未完成)
void rearrange_BF()
{
struct free_block_type *tmp,*work;
printf("Rearrange free blocks for BF\n");
tmp=free_block;
while(tmp!=NULL)
{
work=tmp->next;
while(work!=NULL)
{

}
}

}

*/
/*按WF算法重新整理内存空闲块链表(未完成)
void rearrange_WF()
{
struct free_block_type *tmp,*work;
printf("Rearrange free blocks for WF \n");
tmp=free_block;
while(tmp!=NULL)
{
work=tmp->next;
while(work!=NULL)
{

}
}
}
*/

/*按指定的算法整理内存空闲块链表*/
int rearrange(int algorithm)
{
switch(algorithm)
{
case MA_FF: rearrange_FF(); break;
/*case MA_BF: rearrange_BF(); break; */
/*case MA_WF: rearrange_WF(); break; */
}
}

/*创建新的进程，主要是获取内存的申请数量*/
int new_process()
{
struct allocated_block *ab;
int size;
int ret;
ab=(struct allocated_block *)malloc(sizeof(struct allocated_block));
if(!ab)
exit(-5);
ab->next = NULL;
pid++;
sprintf(ab->process_name, "PROCESS-%02d", pid);
ab->pid = pid;

printf("Memory for %s:", ab->process_name);
scanf("%d", &size);
if(size>0) ab->size=size;
ret = allocate_mem(ab); /* 从空闲区分配内存，ret==1表示分配ok*/
/*如果此时allocated_block_head尚未赋值，则赋值*/
if((ret==1) &&(allocated_block_head == NULL))
{
allocated_block_head=ab;
return 1;
}
/*分配成功，将该已分配块的描述插入已分配链表*/
else if (ret==1)
{
ab->next=allocated_block_head;
allocated_block_head=ab;
return 2;
}
else if(ret==-1)
{ /*分配不成功*/
printf("Allocation fail\n");
free(ab);
return -1;
}
return 3;
}

/*分配内存模块*/
int allocate_mem(struct allocated_block *ab)
{
struct free_block_type *fbt,*pre,*r;
int request_size=ab->size;
fbt=pre=free_block;
while(fbt!=NULL)
{
if(fbt->size>=request_size)
{
if(fbt->size-request_size>=MIN_SLICE)
{
fbt->size=fbt->size-request_size;
}
/*分配后空闲空间足够大，则分割*/

else
{
r=fbt;
pre->next=fbt->next;
free(r);
/*分割后空闲区成为小碎片，一起分配*/

return 1;
}
}
pre = fbt;
fbt = fbt->next;
}

return -1;
}

/*将ab所表示的已分配区归还，并进行可能的合并*/
int free_mem(struct allocated_block *ab)
{
int algorithm = ma_algorithm;
struct free_block_type *fbt, *pre, *work;

fbt=(struct free_block_type*) malloc(sizeof(struct free_block_type));
if(!fbt)
return -1;
fbt->size = ab->size;
fbt->start_addr = ab->start_addr;
/*插入到空闲区链表的头部并将空闲区按地址递增的次序排列*/
fbt->next = free_block;
free_block=fbt;
rearrange(MA_FF);
fbt=free_block;
while(fbt!=NULL)
{
work = fbt->next;
if(work!=NULL)
{
/*如果当前空闲区与后面的空闲区相连，则合并*/
if(fbt->start_addr+fbt->size == work->start_addr)
{
fbt->size += work->size;
fbt->next = work->next;
free(work);
continue;
}
}
fbt = fbt->next;
}
rearrange(algorithm); /*重新按当前的算法排列空闲区*/
return 1;
}

/*?释放ab数据结构节点*/
int dispose(struct allocated_block *free_ab)
{
struct allocated_block *pre, *ab;

if(free_ab == allocated_block_head)
{ /*如果要释放第一个节点*/
allocated_block_head = allocated_block_head->next;
free(free_ab);
return 1;
}
pre = allocated_block_head;
ab = allocated_block_head->next;

while(ab!=free_ab)
{
pre = ab;
ab = ab->next;
}
pre->next = ab->next;
free(ab);
return 2;
}
/*查找要删除的进程*/
struct allocated_block* find_process(int pid)
{
struct allocated_block *temp;
temp=allocated_block_head;
while(temp!=NULL)
{
if(temp->pid==pid)
{
return temp;
}
temp=temp->next;
}
}

/*删除进程，归还分配的存储空间，并删除描述该进程内存分配的节点*/
void kill_process()
{
struct allocated_block *ab;
int pid;
printf("Kill Process, pid=");
scanf("%d", &pid);
ab=find_process(pid);
if(ab!=NULL)
{
free_mem(ab); /*释放ab所表示的分配区*/
dispose(ab); /*释放ab数据结构节点*/

}
}

/* 显示当前内存的使用情况，包括空闲区的情况和已经分配的情况 */

int display_mem_usage()
{
struct free_block_type *fbt=free_block;
struct allocated_block *ab=allocated_block_head;
if(fbt==NULL) return(-1);
printf("----------------------------------------------------------\n");

/* 显示空闲区 */
printf("Free Memory:\n");
printf("%20s %20s\n", " start_addr", " size");
while(fbt!=NULL)
{
printf("%20d %20d\n", fbt->start_addr, fbt->size);
fbt=fbt->next;
}
/* 显示已分配区 */
printf("\nUsed Memory:\n");
printf("%10s %20s %10s %10s\n", "PID", "ProcessName", "start_addr", " size");
while(ab!=NULL)
{
printf("%10d %20s %10d %10d\n", ab->pid, ab->process_name, ab->start_addr, ab->size);
ab=ab->next;
}
printf("----------------------------------------------------------\n");
return 0;
}

**********************************************************************
楼主啊，小女子给你的是残缺版滴，要是你给我分，我就把剩下滴给你,上次在北京大学贴吧都被人骗了，世道炎凉啊O(∩_∩)O~

⑶ 页面置换算法

  上文说到，请求分页管理方式中，当需要调入页面到内存中，但此时内存已满，就需要从内存中按照一定的置换算法决定将哪个页面取出将内存给调入的页面。本文将介绍几种页面置换算方法。
   本文内容

  算法思想：每次选择 淘汰的页面 将是 以后永不使用 ，或者 在最长时间内不再被访问的页面 ，这样可以保证最低的缺页率。
  举例说明，假设系统为进程分配了三个内存块，并考虑到有以下页面号引用串（会依次访问这些页面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

  ....按照此算法依次执行，最后的结果如下

  结果图

  注：缺页时未必发生页面置换，若还有可用的空闲内存空间就不用进行页面置换。
  最佳置换算法可以保证最低的缺页率，但是实际上，只有进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面的访问序列。因此， 最佳置换算法是无法实现的 。

  算法思想：每次选择 淘汰的页面是最早进入内存的页面。
  该算法很简单，每次淘汰最在内存中待时间最久的各个，下面分别给出系统为进程分为配三个内存块和四个内存块的执行情况图。访问序列为3,2,1,0,3,2,4,3,2,1,0,4
  分配三个内存块的情况：

  分配四个内存块的情况：

  当为进程分配的物理块数增大时，缺页次数不减反增的异常现象称为 贝莱迪（Belay）异常 。
   只有FIFO算法会产生Belay异常。 另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应。因为先进入的页面也有可能最经常被访问。因此， 算法性能差。

  算法思想： 每次淘汰的页面是最近最久未使用的页面。
  实现方法：赋予每个页面对应的页表项中，用 访问字段记录该页面纯亏自上次被访问以来所经历的时间t。 当需要淘汰一个页面时，选择现有页面中t最大的页面，即最近最久未使用。

  举例说明，加入某系统为某进程分配了四个内存块，并考虑到有以下页面号引用串：1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7
  这里先直接给出答案

  结果图

  最佳置换算法那性能最好，但无法实现。先进先出置换算法实现简单，但是算法性能差。最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。 时钟置换算法 是一种 性能和开销均春裤配平衡 的算法。又称 CLOCK算法 ，或 最近未用算法 （ NRU ，Not Recently Used）
   简单CLOCK算法 算法思想：为每个页面设置一个 访问位 ，再将内存中的页面都通过 链接指针链接成一个循环队列 。当某个页被访问时，其访问位置1.当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，暂不换出，将访问位改为0，继续检查下一个页面，若第一轮扫描中所有的页面都是1，则将这些页面的访问位一次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个扒指淘汰页面最多会经过 两轮扫描 ）。

  这个算法指针在扫描的过程就像时钟一样转圈，才被称为时钟置换算法。

  简单的时钟置换算法仅考虑到了一个页面最近是否被访问过。事实上，如果淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。 只有淘汰的页面被修改过时，才需要写回外存。
  因此，除了考虑一个页面最近有没有被访问过之外，操作系统还需要考虑页面有没有被修改过。
  改进型时钟置换算法的 算法思想 ： 在其他在条件相同时，应该优先淘汰没有被修改过的页面， 从而来避免I/O操作。
  为了方便讨论，用（访问位，修改位）的形式表示各页面的状态。如（1,1）表示一个页面近期被访问过，且被修改过。
   算法规则 ：将所有可能被置换的页面排成一个循环队列

  由于第二轮已将所有的页的访问位都设为0，因此第三轮、第四轮扫描一定会选中一个页，因此 改进型CLOCK置换算法最多会进行四轮扫描。

  假设系统为进程分配了5个内存块，某时刻，各个页的状态如下图

  如果此时有新的页要进入内存，开始第一轮扫描就找到了要替换的页，即最下面的状态为（0,0）的页。

  某一时刻页面状态如下

  如果此时有新的页要进入内存，开始第一轮扫描就发现没有状态为（0，0）的页，第一轮扫描后不修改任何标志位。所以各个页状态和上图一样。
  然后开始第二轮扫描，尝试找到状态为（0,1）的页，并将扫描过后的页的访问位设为0，第二轮扫描找到了要替换的页。

  某一时刻页面状态如下

  第一轮扫描没有找到状态为（0,0）的页，且第一轮扫描不修改任何标志位，所以第一轮扫描后状态和上图一致。
  然后开始第二轮扫描，尝试找状态为（0,1）的页，也没有找到，第二轮扫描需要将访问位设为1，第二轮扫描后，状态为下图

  某一时刻页面状态如下

  具体的扫描过程和上面相同，这里只给出最后的结果，如下图

  所以，改进型的CLOCK置换算法最多需要四轮扫描确定要置换的页。从上面的分析可以看出，改进型的CLOCK置换算法
  (1) 第一优先级淘汰的是 最近没有访问且没有修改 的页面。
  (2) 第二优先级淘汰的是 最近没有访问但修改 的页面。
  (3) 第三优先级淘汰的是 最近访问但没有修改 的页面。
  (4) 第四优先级淘汰的是 最近访问且修改 的页面。

⑷ 页式管理的请求页式管理中的置换算法

功能：需要调入页面时，选择内存中哪个物理页面被置换。称为replacement policy。
出发点：把未来不再使用的或短期内较少使用的页面调出，通常只能在局部性原理指导下依据过去的统计数据进行预测。
页面锁定(frame locking)：用于描述必须常驻内存的操作系统的关键部分或时间关键(time-critical)的应用进程。实现方法为在页表中加上锁定标志位(lock bit)。 轮转法(RR,round robin)和先进先出算法(FIFO,first in first out):轮转法循回换出内存可用区内一个可以被换出的页，无论该页是刚被换进或已换进内存很长时间。FIFO算法总是选择在内存驻留时间最长的一员将其淘汰。
FIFO算法认为先调入内存的页不再被访问的可能性要比其它页大，因而选择最先调入内存的页换出。实现FIFO算法需要把各个已分配页面按分配时间顺序链接起来，组成FIFO队列，并设置一置换指针指向FIFO队列的队首页面。这样，当要进行置换时，只需把置换指针所指的FIFO队列前头的页顺次换出，而把换入的页链接在FIFO队尾即可。
由实验和测试发现FIPO算法和RR算法的内存利用率不高。这是因为，这两种算法都是基于CPU按线性顺序访问地址空间这一假设。事实上，许多时候．CPU不是按线性顺序访问地址空间的。
Belady现象:一般来说，对于任一作业或进程，如果给它分配的内存页面数越接近于它所要求的页面数，则发生缺页的次数会越少。在极限情况下，这个推论是成立的。因为如果给一个进程分配了它所要求的全部页面，则不会发生缺页现象。但是，使用FIFO算法时，在未给进程或作业分配足它所要求的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。这种现象称为Belady现象。 最近最久未使用页面置换算法(LRU, Least Recently Used):
选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销太大。硬件机构如：
(1) 一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是最久未使用页面。
(2) 每个页面设立移位寄存器：被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。
比较常用的近似算法有：
(a) 最不经常使用页面淘汰算法(LFU, Least Frequently Used)
(b) 最近没有使用页面淘汰(NRU, Not Recently Used) 理想型淘汰算法（OPT,Optimal Replacement Algorithm）
该算法淘汰在访问串中将来再也不出现的或是离当前最远的位置上出现的页。它是一种理想化的算法，性能最好，但在实际上难于实现。

⑸ 几种页面置换算法的基本原理及实现方法

收藏推荐 在多道程序的正常运行过程中,属于不同进程的页面被分散存放在主存页框中,当正在运行的进程所访问的页面不在内存时,系统会发生缺页中断,在缺页中断服务程序中会将所缺的页面调入内存,如内存已无空闲页框,缺页中断服务程序就会调用页面置换算法,页面置换算法的目的就是选出一个被淘汰的页面.把内存和外存统一管理的真正目的是把那些被访问概率非常高的页存放在内存中.因此,置换算法应该置换那些被访问概率最低的页,将它们移出内存.1最佳置换算法基本原理:淘汰以后不再需要的或最远的将来才会用到的页面.这是1966年Belady提出的理想算法,但无法实现,主要用于评价其他置换算法.例:分配给某进程的内存页面数是3页,页面地址流如下:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,其内存动态分配过程如下:7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 17 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 20 0 0 0 0 0 4 4 4 0 0 0 0 0 0 01 1 1 3 3 3 3 3 3 3 3 1 1 1 12先进先出置换......(本文共计2页) 如何获取本文>>

⑹ lru页面置换算法是什么

用双向链表和哈希表来实现。

LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。

反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是着名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，只需要在每次调换时，找到最近最少使用的那个页面调出内存。这就是LRU算法的全部内容。

一种LRU近似算法是最近未使用算法。

它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在之前最近一段时间里它未被访问过。

以上内容参考：网络-页面置换算法

⑺ 操作系统课程设计，用C#实现内存页面的置换。实现算法间比较

页面置换算法

一．题目要求：

通过实现页面置换算法的FIFO和LRU两种算法，理解进程运行时系统是怎样选择换出页面的，对于两种不同的算法各自的优缺点是哪些。

要求设计主界面以灵活选择某算法，且以下算法都要实现 1) 最佳置换算法(OPT)：将以后永不使用的或许是在最长(未来)时间内不再被访问的页面换出。

2) 先进先出算法(FIFO)：淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

3) 最近最久未使用算法(LRU)：淘汰最近最久未被使用的页面。 4) 最不经常使用算法(LFU) 二．实验目的：

1、用C语言编写OPT、FIFO、LRU，LFU四种置换算法。 2、熟悉内存分页管理策略。 3、了解页面置换的算法。 4、掌握一般常用的调度算法。 5、根据方案使算法得以模拟实现。 6、锻炼知识的运用能力和实践能力。 三、设计要求

1、编写算法，实现页面置换算法FIFO、LRU；

2、针对内存地址引用串，运行页面置换算法进行页面置换； 3、算法所需的各种参数由输入产生（手工输入或者随机数产生）； 4、输出内存驻留的页面集合，页错误次数以及页错误率；

四．相关知识：

1．虚拟存储器的引入：

局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。

2．虚拟存储器的定义：

虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。

3．虚拟存储器的实现方式：

分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。

请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。

4．页面分配：

平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。 按比例分配算法，根据进程的大小按比例分配物理块。

考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。

5．页面置换算法：

常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等。 五、设计说明

1、采用数组页面的页号

2、FIFO算法，选择在内存中驻留时间最久的页面予以淘汰；

分配n个物理块给进程，运行时先把前n个不同页面一起装入内存，然后再从后面逐一比较，输出页面及页错误数和页错误率。

3、LRU算法，根据页面调入内存后的使用情况进行决策；

同样分配n个物理块给进程，前n个不同页面一起装入内存，后面步骤与前一算法类似。

选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换： 六．设计思想：

OPT基本思想：

是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组next[mSIZE]记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。

FIFO基本思想：

是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数组time[mSIZE]记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。

LRU基本思想：

是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组flag[10]标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。 七．流程图：

如下页所示

六．运行结果： 1. 按任意键进行初始化：

2. 载入数据：

3. 进入置换算法选择界面：

4.运算中延迟操作：

5.三种算法演示结果：

⑻ 用C++语言编写FIFO页面置换算法代码

分别使用FIFO、OPT、LRU三种置换算法来模拟页面置换的过程。（Linux、Windows下皆可）
输入：3//页帧数
70120304230321201701//待处理的页
输出：页面置换过程中各帧的变化过程和出现页错误的次数
[cpp]
#include<iostream>
usingnamespacestd;
intinput[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
classpage
{
public:
intnum;
intmark;
page()
{
num=0;
mark=21;
}
};
voidFIFO()
{
cout<<"------FIFO-----------"<<endl;
interror=0;
pageframe[3];//页帧
for(inti=0;i<3;i++)//处理前三个引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
frame[((error-1)%3)].num=input[i];//换掉最旧的页
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
voidOPT()
{
cout<<"------OPT------------"<<endl;
interror=0;
pageframe[3];
for(inti=0;i<3;i++)//处理前三个引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
for(j=0;j<3;j++)
{
frame[j].mark=21;
for(intk=20;k>=i;k--)//向后遍历，找到最长时间不用的页
{
if(frame[j].num==input[k])
frame[j].mark=k;
}
}
if(frame[0].mark>frame[1].mark&&frame[0].mark>frame[2].mark)
frame[0].num=input[i];
elseif(frame[1].mark>frame[0].mark&&frame[1].mark>frame[2].mark)
frame[1].num=input[i];
else
frame[2].num=input[i];
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
voidLRU()
{
cout<<"------LRU------------"<<endl;
interror=0;
pageframe[3];
for(inti=0;i<3;i++)//处理前三个引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
for(j=0;j<3;j++)
{
frame[j].mark=0;
for(intk=0;k<=i;k++)//向前遍历，找到最近最少使用的
{
if(frame[j].num==input[k])
frame[j].mark=k;
}
}
if(frame[0].mark<frame[1].mark&&frame[0].mark<frame[2].mark)
frame[0].num=input[i];
elseif(frame[1].mark<frame[0].mark&&frame[1].mark<frame[2].mark)
frame[1].num=input[i];
else
frame[2].num=input[i];
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
intmain()
{
FIFO();
OPT();
LRU();
}