lru演算法的模擬
A. LRu演算法具體步驟
內存已有頁面 需要頁面 操作 內存結果頁面 頁面是否失效
1 加入內存 1 否
8 加入內存 18 否
1 18 否
7 加入內存 718 否
8 871 否
2 加入內存 2871 否
7 7281 否
2 2781 否
1 1278 否
8 8127 否
3 換出7 3812 是
8 8312 否
2 2831 否
1 1283 否
3 3128 否
1 1328 否
7 換出8 7132 是
1 1732 否
3 3172 否
7 7312 否
頁面失效2次。
B. 給出一種高級語言實現LRU演算法和FIFO演算法的源程序。
/*
* Created on 2004-12-25
*
* TODO To change the template for this generated file go to
* Window - Preferences - java - Code Style - Code Templates
*/
/**
* @Michelangelo
*
* TODO To change the template for this generated type comment go to
* Window - Preferences - Java - Code Style - Code Templates
*/
import java.util.*;
public class TestReplacement {
/**
*
*/
private final int ArraySize=20;
private int digitalArray[]=new int [ArraySize];
//private int digitalArray[]={1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6};
private static final int frameSize[]={1,2,3,4,5,6,7};
private static int errorCount=0;
Vector frame=new Vector();
public TestReplacement() {
super();
// TODO Auto-generated constructor stub
}
public static void main(String[] args) {
TestReplacement aT=new TestReplacement();
aT.generateRandomDigit();
aT.output();
System.out.println("-------------Using FIFO--------------");
System.out.println();
for(int i=0;i<frameSize.length;i++){
System.out.println("Frame size: "+frameSize[i]+"\n");
aT.initFrameForFIFO(frameSize[i]);
aT.FIFOReplace(frameSize[i]);
System.out.println("Total errors found: "+errorCount);
System.out.println("\n************************************\n");
errorCount=0;
}
System.out.println();
System.out.println("----------------Using LRU----------------");
System.out.println();
for(int i=0;i<frameSize.length;i++){
System.out.println("Frame size: "+frameSize[i]+"\n");
aT.initFrameForLRU(frameSize[i]);
aT.LRUReplace(frameSize[i]);
System.out.println("Total errors found: "+errorCount);
System.out.println("\n************************************\n");
errorCount=0;
}
}
public void generateRandomDigit(){
for(int i=0;i<ArraySize;i++){
digitalArray[i]=(int)Math.round(Math.random()*9);
}
}
public void output(){
System.out.println("隨機序列：");
for(int i=0;i<ArraySize;i++){
System.out.print(" "+digitalArray[i]);
}
System.out.println();
}
public void initFrameForFIFO(int fS){
frame.removeAllElements();
for(int i=0;i<fS;i++){
frame.addElement(new Couple(fS-i));
}
}
public void initFrameForLRU(int fS){
frame.removeAllElements();
for(int i=0;i<fS;i++){
frame.addElement(new Couple(0));
}
}
public void LRUReplace(int fS){
boolean findThesame=false;
int pre=-1;//存放剛剛查找到的位置
int flag=-1;
for(int j=0;j<digitalArray.length;j++){
boolean match=false;
for(int i=0;i<fS;i++){
if(((Couple)frame.elementAt(i)).value==digitalArray[j]){
((Couple)frame.elementAt(i)).time=0;
match=true;//是否找到匹配
System.out.println(j+": find "+((Couple)frame.elementAt(i)).value+" "+"at location "+i);
System.out.println();
flag=i;
break;
}
}
if(match==true&&flag!=pre){
for(int i=0;i<fS;i++){
if(i!=flag){
((Couple)frame.elementAt(i)).time--;
}
}
pre=flag;
}
else if(match==false){
int temp=0;
int index=0;
for(int i=0;i<fS;i++){
if(((Couple)frame.elementAt(i)).time<temp){
temp=((Couple)frame.elementAt(i)).time;
index=i;
}
}
for(int i=0;i<fS;i++){
if(i!=index){
((Couple)frame.elementAt(i)).time--;
}
else{
((Couple)frame.elementAt(i)).time=0;
System.out.print(j+": replace "+((Couple)frame.elementAt(i)).value+" ");
System.out.print("at location "+index+" ");
((Couple)frame.elementAt(i)).value=digitalArray[j];
System.out.println("with "+((Couple)frame.elementAt(i)).value);
errorCount++;
System.out.println("error count "+errorCount);
System.out.println();
}
}
}
}
}
public void FIFOReplace(int fS){
//boolean blank=true;//是否開始的已填充完
int i=0;
for(int j=0;j<digitalArray.length;j++){
boolean match=false;
for(i=0;i<fS;i++){
if(((Couple)frame.elementAt(i)).value==digitalArray[j]){
match=true;//是否找到匹配
System.out.println(j+": find "+((Couple)frame.elementAt(i)).value+" "+"at location "+i);
break;
}
}
if(match==false){
int temp=0;
int index=-1;
for(i=0;i<fS;i++){
if(((Couple)frame.elementAt(i)).time>temp){
temp=((Couple)frame.elementAt(i)).time;
index=i;
}
}
for(i=0;i<fS;i++){
if(i==index){
System.out.print(j+": replace "+((Couple)frame.elementAt(i)).value+" ");
System.out.print("at location "+i+" ");
((Couple)frame.elementAt(i)).value=digitalArray[j];
System.out.println("with "+((Couple)frame.elementAt(i)).value);
((Couple)frame.elementAt(i)).time=1;
errorCount++;
System.out.println("error count "+errorCount);
System.out.println();
}
else{
((Couple)frame.elementAt(i)).time++;
}
}
}
}
}
}
class Couple{
public int value=-1;
public int time=-1;
public Couple(int t){
time=t;
}
}
演算法思想：用Vector來模擬頁表，而扔進去的Couple的個數就是表的大小。Couple 中的Time設置衰老時間（FIFO）或未使用周期（LRU），Value為請求序列中digitalArray[]的值。序列長為20由隨機函數產生的0-9的整型值。frameSize[]中存放的是頁表的大小（也就是對應著扔幾個Couple進去啦）
FIFO：初始化時先清空然後放Couple，將他們的Time屬性按放的順序分別置為frameSize,frame-1,frame-2.......1.數值越大放的越早,value通通置-1。接下來的工作就是對value和time的處置。若在vector中的couple的value里找到了value匹配則pass。如果沒有找的話就從中time里找最老的，（誰的time最大就最老），找到後把它的value變成相應的請求的頁面值，把它的time=1.對於不是最老的呢，就把他們的歲數都加一吧。
LRU:初始化時先清空然後放Couple,將他們的Time屬性置-1，value通通置-1。接下來處理請求序列了。若在value里找到對應的頁面話就把對應的Time置0。其他的Couple對應的time- -。如果沒有找到的話就找一個最近使用的最少的啦（就是對應的time最負的那個），找到以後就把它的Value換成請求的頁面值並且把它的time置0.與此同時，其他的time--。
C. lru演算法是什麼
最近最少使用頁面置換演算法，是為虛擬頁式存儲管理服務的。
LRU演算法的建議基於以下事實：在前幾條指令中經常使用的頁面很可能在後幾條指令中經常使用。
相反，長時間未使用的頁面將來可能會長時間不使用。 這是眾所周知的局部性原則-緩存比內存快，它也以相同的原理運行。 因此，每次交換時，我們只需要找到使用最少的頁面來調出內存即可。
(3)lru演算法的模擬擴展閱讀：
LRU演算法是大多數操作系統廣泛使用以最大化頁面命中率的頁面替換演算法。該演算法的思想是，當發生頁面錯誤時，將選擇並替換未使用時間最長的頁面。
從程序操作原理的觀點來看，最近最少使用的演算法是相對接近理想的頁面替換演算法。該演算法不僅充分利用了內存中頁面調用的歷史信息，而且可以正確反映程序的局部問題。
D. LRU頁面置換演算法的實現
我會。就是最近未使用的演算法吧。例如一個三道程序，等待進入的是1，2，3，4，4，2，5，6，3，4，2，1。先分別把1，2，3導入，然後導入4，置換的是1，因為他離導入時間最遠。然後又是4，不需要置換，然後是2，也不需要，因為內存中有，到5的時候，因為3最遠，所以置換3，依次類推，還有不懂聯系我吧。QQ：243926566
E. LRU演算法解釋
看我寫的這個,有詳細注釋
.......................................
#include <stdio.h>
#include <stdlib.h>
#define mSIZE 3//分配三個內存頁塊
#define pSIZE 12//總共12個進程
struct mem
{
int num;
int count;
}memery[3]={0,-1,0,-1,0,-1};
static int process[pSIZE] ={1,2,3,4,1,2,5,1,2,3,4,5};//頁面訪問序列
void LRU();
void get();
int main()
{
get();
printf("\n(LRU)\treplace\n");
LRU();
system("PAUSE");
return 0;
}
void get()
{
int w[12]={1,2,3,4,1,2,5,1,2,3,4,5};
int i,n;
for(i=0;i<12;i++)
{
printf("%d ",w[i]);
}
}
void LRU()
{
int i = 0, j = 0,k=0,x,y;
int replace;
for(i = 0; i<pSIZE; i++) //對輸入序列進行循環
{
x=0;y=0; //置x，y初值為0
for(j = 0; j < mSIZE; j++) //對三個內存塊進行循環，先查找有沒有與即將訪問頁號相同的
if(memery[j].num == process[i])
{ x=1;//有相同的則置x為1
replace=process[i];
memery[j].count=0;//置此塊count為0
for(k=0;k<3;k++)
if(k!=j&&memery[k].num!=0)memery[k].count++;//其他不為0頁count++
break;//跳出此次內存塊循環
}
if(x==0)//沒有與即將訪問頁號相同的內存塊
{
for(j = 0; j < mSIZE; j++)//對內存塊循環，查找有沒有空內存塊
if(memery[j].num== 0)
{
y=1;//有則置y為1
replace=0;
memery[j].num=process[i];// 置此內存塊為訪問頁號
memery[j].count=0;//置此塊count為0
for(k=0;k<3;k++)
if(k!=j&&memery[k].num!=0)memery[k].count++;//其他不為0頁count++
break;//跳出此次內存塊循環
}
}
if(x==0&&y==0)//既沒有與即將訪問頁號相同的內存塊也沒有空內存塊
{
int m=memery[0].count;
for(j = 0; j < mSIZE; j++)
{
if(memery[j].count>m)
m=memery[j].count;
}//查找出count最大的內存塊m
for(j=0;j<mSIZE;j++)//對內存塊循環，count=m的內存塊
{
if(memery[j].count==m)
{
replace=memery[j].num;
memery[j].num=process[i]; //置此內存塊為訪問頁號塊
memery[j].count=0;//置此塊count為0
}
else memery[j].count++;//其他塊count++
}
}
for(j = 0 ;j < mSIZE; j++) //列印每次訪問後的情況
printf("%d ",memery[j].num);
printf("\t%d\n",replace);
}
}
F. lru 演算法一題
物理頁面就是一次能存放的最多頁面數，LRU演算法是淘汰最久未使用的頁面。給你具體的計算過程吧：
順序：1 2 3 4 5 6 7 8 9 10 11 12
頁面：3 5 2 3 4 7 4 9 1 3 8 3
M（5):3 5 2 3 4 7 4 9 1 3 8 3
3 5 2 3 4 7 4 9 1 3 8
3 5 2 3 3 7 4 9 1 1
5 2 2 3 7 4 9 9
5 5 2 3 7 4 4
F： + + + + + + + +
缺頁數：8（F為+代表缺頁）缺頁率：8/12
G. 實現LRU演算法的硬體支持是什麼
寄存器、棧
實現LRU演算法的硬體支持是寄存器、棧。寄存器用於記錄某進程在內存中各頁的使用情況；棧用於保存當前使用的各個頁面的頁面號。LRU是最近最少使用，是一種常用的頁面置換演算法，選擇最近最久未使用的頁面予以淘汰。寄存器的功能是存儲二進制代碼，它是由具有存儲功能的觸發器組合起來構成的。一個觸發器可以存儲1位二進制代碼，故存放n位二進制代碼的寄存器，需用n個觸發器來構成。
(7)lru演算法的模擬擴展閱讀：
大部分操作系統為最大化頁面命中率而廣泛採用的一種頁面置換演算法是LRU演算法。該演算法的思路是，發生缺頁中斷時，選擇未使用時間最長的頁面置換出去。從程序運行的原理來看，最近最少使用演算法是比較接近理想的一種頁面置換演算法，這種演算法既充分利用了內存中頁面調用的歷史信息，又正確反映了程序的局部問題。
H. 操作系統LRU演算法習題求解！！！
LRU隊列長度為 （384/128) = 3。
87、138、277、56、390、532、285、410、45、180、330、190
對應的頁面號依次為：
0 、 1 、 2 、 0 、 3 、 4 、 2 、 3 、 0 、 1 、 2 、 1
然後看看那幾個頁面會缺頁：
0、1、2 都會缺頁，因為一開始內存裡面什麼頁面都沒有。
0會命中。 現在內存裡面頁面的LRU順序為0，2，1
3、4都會缺頁。 內存中沒有。 現在內存裡面LRU順序為 4，3，0
2會缺頁。 內存中沒有。 LRU順序為 2，4，3
0、1會缺頁。 內存中沒有。 LRU順序為 1，0，2
2、1會命中。
總共12次訪問，只有3次命中，9次失效。
失效率為 9/12 = 75%
I. LRU演算法具體怎麼算的，有沒有例子
有例子 LRU（least recently used）最近最久未使用。
假設 序列為 4 3 4 2 3 1 4 2
物理塊有3個 則
首輪 4調入內存 4
次輪 3調入內存 3 4
之後 4調入內存 4 3
之後 2調入內存 2 4 3
之後 3調入內存 3 2 4
之後 1調入內存 1 3 2（因為最近最久未使用的是4，從這里向前找最近最久未使用的）
之後 4調入內存 4 1 3（原理同上）
最後 2調入內存 2 4 1
過程就是這樣的，樓主只要明白最近最久未使用這個道理，再回去參考書上的例子就明白是怎麼算的啦！呵呵！