os缺页置换算法

A. 操作系统页面置换算法

先进先出FIFO：（0代表未被占用）
（1）1，0，0，0（2）1，2，0，0（3）1，2，3，0（4）1，2，3，4（5）1，2，3，4访问2（6）1，2，3，4访问1（7）5，2，3，4访问5替换1（8）5，6，3，4访问6替换2（9）5，6，2，4访问2替换3（10）5，6，2，1访问1替换4（11）5，6，2，1访问2（12）3，6，2，1访问3替换5（13）3，7，2，1访问7替换6（14）3，7，6，1访问6替换2（15）3，7，6，1访问3（16）3，7，6，2访问2替换1（16）1，7，6，2访问1替换3（17）1，7，6，2访问2（18）1，3，6，2访问3替换7（20）1，3，6，2访问6
缺页率为：14/20=0.7

最近最久未使用LRU：（0代表未被占用）
（1）1，0，0，0（2）1，2，0，0（3）1，2，3，0（4）1，2，3，4（5）1，2，3，4访问2（6）1，2，3，4访问1（7）1，2，5，4访问5替换3（8）1，2，5，6访问6替换4（9）1，2，5，6访问2（10）1，2，5，6访问1（11）1，2，5，6访问2（12）1，2，3，6访问3替换5（13）1，2，3，7访问7替换6（14）6，2，3，7访问6替换1（15）6，2，3，7访问3（16）6，2，3，7访问2（17）6，2，3，1访问1替换7（18）6，2，3，1访问2（19）6，2，3，1访问3（20）6，2，3，1访问6
缺页率为：10/20=0.5

最佳置换算法OPT：（0代表未被占用）
（1）1，0，0，0（2）1，2，0，0（3）1，2，3，0（4）1，2，3，4（5）1，2，3，4访问2（6）1，2，3，4访问1（7）1，2，3，5访问5替换4（8）1，2，3，6访问6替换5（9）1，2，3，6访问2（10)1，2，3，6访问1（11）1，2，3，6访问2（12）1，2，3，6访问3（13）7，2，3，6访问7替换1（14）7，2，3，6访问6（15）7，2，3，6访问3（16）7，2，3，6访问2（17）1，2，3，6访问1替换7（18）1，2，3，6访问2（19）1，2，3，6访问3（20）1，2，3，6访问6
缺页率为：8/20=0.4

B. 操作系统 页面置换算法LRU

这两种方法都正确，LRU算法有几种实现，前一种是基于计数器的，需要统计之前的引用页，后一种是基于队列的调度，只调整队列就能找到最近未使用的页。
如果是考试的话可以说明一下用了哪种方法，个人感觉第二种方法比较合适
《操作系统概念》第七版·高等教育出版社P286

C. 求用c++程序设计的实验:模拟分页式存储管理中硬件的地址转换和用先进先出调度算法(FIFO)处理缺页中断。

#include<iostream.h>
#include<stdlib.h>
#include<iomanip.h>
#include"windows.h"
#include"os.h"
#define n 64//实验中假定主存的长度
#define m 4//实验中假定每个作业分得主存块块数
int p[m];//定义页
struct
{
short int lnumber;//页号
short int flag;//表示该页是否在主存，“1”表示在主存，“0”表示不在主存
short int pnumber;//该页所在主存块的块号
short int write;//该页是否被修改过，“1”表示修改过，“0”表示没有修改过
short int dnumber;//该页存放在磁盘上的位置，即磁盘块号
short int times;//被访问的次数，用于LRU算法
}page[n];//定义页表
//各个函数的实现如下：
computer::computer()
{
int i;
for(i=0;i<n;i++)
{
page[i].lnumber = i;
page[i].flag = 0;
page[i].pnumber = 10000;//用10000表示为空
page[i].write = 0;
page[i].dnumber = i;
page[i].times = 0;
}//初始化页表

for(i=0;i<m;i++)
{
page[i].pnumber = i;
}

for(i=0;i<m;i++)
{
p[i] = i;
page[i].flag = 1;
}//初始化页
}
void computer::showpagelist()
{
int i;
cout<<"页号"<<"\t"<<"是否在主存中"<<"\t"<<"块 号"<<"\t"<<"是否被修改过"<<"\t"<<"磁盘块号"<<"\t"<<"访问次数"<<endl;
for(i=0;i<n;i++)
{
cout<<page[i].lnumber<<"\t"<<page[i].flag<<" "<<page[i].pnumber<<"\t"<<page[i].write<<" "<<page[i].dnumber<<" \t"<<page[i].times<<endl;
}
}
void computer::showpage()
{
int i;
for(i=0;i<m;i++)
{
cout<<"\t"<<p[i];
}
cout<<endl;
}
void computer::transformation()
{
unsigned logicAddress,logicNumber,innerAddress,physicsAddress,physicsNumber;
int i,head=0,fail = 0;
int method,temppage=0;
short int times = 10000;
cout<<"请输入一个逻辑地址（四位十六进制数）:";
cin>>hex>>logicAddress;//读入逻辑地址
logicNumber = logicAddress >> 10;//得到页号
cout<<"页号为:"<<logicNumber<<endl;
innerAddress = logicAddress & 0x03ff;//得到页内地址
cout<<"页内地址为:"<<innerAddress<<endl;
for(i=0;i<n;i++)
{
if(logicNumber==(unsigned)page[i].lnumber)
{
if(page[i].flag == 1)
{
cout<<"请求的页面在主存中!"<<endl;
page[i].times++;
physicsNumber = page[i].pnumber;//由页号得到块号
cout<<"请求的主存块号为:"<<physicsNumber<<endl;
physicsAddress = physicsNumber << 10 |innerAddress;//得到物理地址
cout<<"请求的物理地址为:"<<physicsAddress<<endl;//输出物理地址
break;
}
else
{

cout<<"请求的页面不在主存中! 将进行缺页中断处理!"<<endl<<"请选择算法!"<<endl;
cout<<"1.先进先出"<<endl<<"2.最近最少用"<<endl<<"请选择置换算法:";
cin>>method;
if(method == 1) //采用先进先出算法
{
cout<<"采用先进先出算法!"<<endl;
fail = p[head];
cout<<"第"<<fail<<"页将被替换!"<<endl;
p[head] = logicNumber;
head = (head+1) % m;
if(page[fail].write == 1)
cout<<"第"<<fail<<"页曾被修改过!"<<endl;
page[fail].flag = 0;
page[logicNumber].flag = 1;
page[logicNumber].write = 0;
page[logicNumber].pnumber = page[fail].pnumber;
page[fail].pnumber = 10000;
page[logicNumber].times++;
break;
}
else if(method == 2) //采用最近最少用算法
{
cout<<"采用最近最少用算法!"<<endl;
for(i=0;i<n;i++)
{
if(page[i].flag == 1)
{
if(page[i].times<times)
{
times = page[i].times;
temppage = page[i].lnumber;
}
}
}
cout<<"第"<<temppage<<"页将被替换!"<<endl;
for(i=0;i<m;i++)
{
if(p[i] == temppage)
{
p[i] = logicNumber;
}
}
if(page[temppage].write == 1)
cout<<"第"<<temppage<<"页曾被修改过!"<<endl;
page[temppage].flag = 0;
page[logicNumber].flag = 1;
page[logicNumber].write = 0;
page[logicNumber].pnumber = page[temppage].pnumber;
page[temppage].pnumber = 10000;
page[logicNumber].times++;
break;
}
else
{ cout<<"你输入有误，即将退出!";
exit(1);
}
}
}
}
}
void main()
{
char c,d;
computer os;
cout<<"页表正在初始化中...，3秒钟后为你显示页和页表！"<<endl;
Sleep(3000);
os.showpage();
os.showpagelist();
T:
os.transformation();
cout<<"是否显示页和页表？（Y/N）";
cin>>c;
switch(c)
{
case 'y':
os.showpage();
os.showpagelist();
case 'n':
cout<<"是否继续进行请求分页？（Y/N）";
cin>>d;
if (d=='Y'||d=='y')
goto T;
else if (d=='N'||d=='n')
exit(1);
else
cout<<"输入错误！"<<endl;
default:cout<<"输入错误！"<<endl;
}

}

D. 操作系统 页式管理中的置换算法 怎么看缺页

去年学过，现在记忆残缺，尽量回答
FIFO算法是先入先出算法吧，首先是有三个页面，所以一列只有三行
再者，根据先入先出的规则，后面读取的串替代内存中进来时间最久的串，若当前读取的串内存中已经有了，则内存中的页面不变
缺页就是没有重复的页面，即没有重复的页面共有10页，就缺页10次
LRU LFU就是看访问串前面或者后面会不会有使用到，具体哪个我忘了，把FIFO看明白了你就晓得了
FIFO：
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1
7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0
空0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1
空空1 1 1 1 0 0 0 3 3 3 3 3 2 2 2
你的打错了吧
PS:我上面说缺页10页是随便举的例子，题目中的缺页数是12，缺页不是很好计算的么，就是没有内容重复的内存页，数一下就知道了，还不知道就留言我吧

E. 页面置换算法的常见的置换算法

最简单的页面置换算法是先入先出（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算法了。

F. 操作系统页面置换算法题，谁会

第二次机会算法：

与FIFO、OPT、LRU、NRU等同为操作系统中请求分页式管理方式的页面置换算法。

第二次机会算法的基本思想是与FIFO相同的，但是有所改进，避免把经常使用的页面置换出去。当选择置换页面时，依然和FIFO一样，选择最早置入内存的页面。但是二次机会法还设置了一个访问状态位。所以还要检查页面的的访问位。如果是0，就淘汰这页；如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前时间。如果该页在此期间被访问过，则访问位置为1。这样给了第二次机会的页面将不被淘汰，直至所有其他页面被淘汰过（或者也给了第二次机会）。因此，如果一个页面经常使用，它的访问位总保持为1，它就从来不会被淘汰出去。

第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个存储块时，指针就前进，直至找到访问位是0的页。随着指针的前进，把访问位就清为0。在最坏的情况下，所有的访问位都是1，指针要通过整个队列一周，每个页都给第二次机会。这时就退化成FIFO算法了。

G. 页面置换算法中的缺页率如何计算

很简单，把每次有新页面走向进入时记录下来。如果下一次进入时改变原先页面的占有情况，则算一次缺页。一般情况下如果页面为3则前三次都算缺页。

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

收藏推荐 在多道程序的正常运行过程中,属于不同进程的页面被分散存放在主存页框中,当正在运行的进程所访问的页面不在内存时,系统会发生缺页中断,在缺页中断服务程序中会将所缺的页面调入内存,如内存已无空闲页框,缺页中断服务程序就会调用页面置换算法,页面置换算法的目的就是选出一个被淘汰的页面.把内存和外存统一管理的真正目的是把那些被访问概率非常高的页存放在内存中.因此,置换算法应该置换那些被访问概率最低的页,将它们移出内存.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页) 如何获取本文>>

I. 计算机操作系统页面置换算法

我的理解，图中为页面的请求序列，首次请求1，3，2，5这四个页面时，均没有命中缓存，产生了一个缺页异常，操作系统加载相应的页面后，下次再请求时就为命中状态。12次请求，有4次缺页，缺页率为4/12=1/3