lru演算法實現

㈠ 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);
}
}

㈡ lru演算法是什麼

lru演算法是一種常用的頁面置換演算法，選擇最近最久未使用的頁面予以淘汰。

該演算法賦予每個頁面一個訪問欄位，用來記錄一個頁面自上次被訪問以來所經歷的時間 t，當須淘汰一個頁面時，選擇現有頁面中其 t 值最大的，即最近最少使用的頁面予以淘汰。

特點：

LRU 置換演算法雖然是一種比較好的演算法，但要求系統有較多的支持硬體。為了了解一個進程在內存中的各個頁面各有多少時間未被進程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有兩類硬體之一的支持：寄存器或棧。

在進程運行過程中，若其所要訪問的頁面不在內存而需把它們調入內存，但內存已無空閑空間時，為了保證該進程能正常運行，系統必須從內存中調出一頁程序或數據送磁碟的對換區中。

㈢ 給出一種高級語言實現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--。

㈣ 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

㈤ 用java語言實現LRU演算法和FIFO演算法。急急急！！！！！！！

您好，網路貼吧專家團很高興能夠回答您的問題。您的採納是我們前進的動力。
public class LRU {

private int theArray[];
private int back; //定義隊尾
private int currentSize; //隊列中存放元素個數
private int maxSize=5; //隊列中能存放元素的個數

public LRU(){
theArray=new int[maxSize];
back=0;
currentSize=0;
}
public void queue(int a[]){
for(int i=0;i<a.length;i++){
enQueue(a[i]);
}
}

public void enQueue(int x){ //入隊
beUsed(x); //先判斷是否已存在該頁號，若存在，刪除
if(currentSize<maxSize){
theArray[back]=x;
back++;
currentSize++;
}else if(currentSize==maxSize){ //滿了
for(int i=0;i<maxSize-1;i++){
theArray[i]=theArray[i+1];
}
theArray[maxSize-1]=x;
}
for(int i=0;i<currentSize;i++){
System.out.print(theArray[i]);
}
System.out.println();
}
public void beUsed(int x){ //判斷是否已存在該頁號,若存在，刪除已有的
for(int i=0;i<currentSize;i++){
if(theArray[i]==x){
for(int j=i;j<currentSize-1;j++){
theArray[j]=theArray[j+1];
}
currentSize--;
back--;
}
}
}
public static void main(String[] args) {
LRU lru=new LRU();
int a[]={4,7,0,7,1,0,1,2,1,2,6};
lru.queue(a);
}

}

㈥ 求LRU演算法流程圖！！！

一行注釋沒有，懶得看

㈦ 實現LRU演算法的硬體支持是什麼

寄存器、棧

實現LRU演算法的硬體支持是寄存器、棧。寄存器用於記錄某進程在內存中各頁的使用情況；棧用於保存當前使用的各個頁面的頁面號。LRU是最近最少使用，是一種常用的頁面置換演算法，選擇最近最久未使用的頁面予以淘汰。寄存器的功能是存儲二進制代碼，它是由具有存儲功能的觸發器組合起來構成的。一個觸發器可以存儲1位二進制代碼，故存放n位二進制代碼的寄存器，需用n個觸發器來構成。

(7)lru演算法實現擴展閱讀：

大部分操作系統為最大化頁面命中率而廣泛採用的一種頁面置換演算法是LRU演算法。該演算法的思路是，發生缺頁中斷時，選擇未使用時間最長的頁面置換出去。從程序運行的原理來看，最近最少使用演算法是比較接近理想的一種頁面置換演算法，這種演算法既充分利用了內存中頁面調用的歷史信息，又正確反映了程序的局部問題。

㈧ 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

過程就是這樣的，樓主只要明白最近最久未使用這個道理，再回去參考書上的例子就明白是怎麼算的啦！呵呵！

㈨ 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次。

㈩ lru緩存演算法用什麼數據結構實現

1、請求分頁的頁表機制，他是在純分頁的頁表機制上增加若干項而形成的，作為請求分頁的數據結構。 2、缺頁中斷機構，即每當用戶程序要訪問的頁面尚未調入時，便產生一缺頁中斷，以請求OS將所缺的頁調入內存。 3、地址變換機構，他同樣是在純分頁