fifo替換演算法

『壹』 操作系統題：頁面置換演算法 OPT FIFO LRU

fifo就是先進先出，可以想像成隊列
lru是最久未使用，當需要替換頁面的時候，向前面看，最久沒使用的那個被替換
opt是替換頁面的時候，優先替換後面最遲出現的。
不懂再問。。

『貳』 用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();
}

『叄』 fifo演算法怎麼寫

用C語言編寫簡單的FIFO置換演算法#include "stdio.h"
#include "malloc.h"
#define OK 1
#define ERROR 0
#define NULL 0
#define status int
typedef int Elemtype;

/*這個定義的是隊列的元素的數據結構*/
typedef struct tailDATA{
Elemtype data;/*這個存放的是隊列元素的值*/
struct tailDATA *next;//指向下一個元素
}datatail,*map;

/*以下定義的是隊列頭的數據結構*/
typedef struct Tail{
/*說明:對隊列進行操作的時候,插入的時候是對front操作,刪除*/
Elemtype data;/*這個記載的是隊列的元素的個數*/
map front;/*這個是隊列的頭*/
map rear;/*這個是隊列的尾*/
}tail,*mappath;

/*以下定義的就是操作了,初始話的操作就不想做了,直接寫個插入和刪除等的一些的演算法就可以了*/
status inserttail(mappath &T,map P)
{/*這個函數的功能是將一個個已知的元素插入隊列中*/
if(T==NULL)
{
T=(mappath)malloc(sizeof(tail));
T->data=0;
T->front=NULL;
T->rear=NULL;
}
if(!P) return OK;
T->rear->next=P;
T->rear=P;
if(!(T->front)) T->front=P;
return OK;
}

status insertdatatail(mappath &T,int a)
{/*這個函數將一個元素插入隊列中,其實這個函數是沒有必要的,但是為了方便起見,還是寫了個*/
if(T==NULL)
{
T=(mappath)malloc(sizeof(tail));
T->data=0;
T->front=NULL;
T->rear=NULL;
map linshi=(map)malloc(sizeof(datatail));
linshi->data=a;
linshi->next=NULL;
T->front=linshi;
T->rear=linshi;
T->data=1;
return OK;
}
map linshi=(map)malloc(sizeof(datatail));
linshi->data=a;
linshi->next=NULL;
T->rear->next=linshi;
T->rear=linshi;
if(!(T->front)) T->front=linshi;
T->data++;
return OK;
}

status deltail(mappath &T)
{/*因為對隊列進行刪除操作的時候,基本上是沒有什麼條件,就是對front做一些相應的操作就可以了
,所以他的函數列表也就比較少了*/
if(!T) return ERROR;/*如果隊列本來就是空的,那麼就返回一個錯誤的信息*/
if(T->front==T->rear)
{/*如果隊列只有一個元素,就執行下面的操作,防止出現了錯誤*/
map linshi=T->front;
free(linshi);
T->data=0;
T->front=NULL;
T->rear=NULL;
return OK;
}
map linshi=T->front;
T->front=T->front->next;
T->data--;
free(linshi);
return OK;
}

status puttail(mappath T)
{/*這個是對一個已經存在的隊列進行輸出*/
if(!T) return ERROR;
printf("the tail'count is %d\n",T->data);
int count=T->data;map q=T->front;
for(int i=0;i<count;i++)
{
printf("%d ",q->data);
q=q->next;
}
return OK;
}

int main()
{
printf("hello,world!\n");
mappath q=NULL;int count1=0;int dataa=0;
printf("please input a number to the count of tail\n");
scanf("%d",&count1);
for(int i=0;i<count1;i++)
{
printf("please input a number to tail\n");
scanf("%d",&dataa);
insertdatatail(q,dataa);
}
puttail(q);
deltail(q);
puttail(q);
return 0;
}

『肆』 計算機組成原理-----替換演算法

fifo先進先出演算法 有abc 三個存儲空間 每個空間能存放一個元素按照隊列方式
進出，以此是 a b c 命中率=abc中訪問到的次數/元素個數
------------------2 1 0 此時存儲空間已滿 要調用新的元素就要出隊列
------------------4 2 1 下一個元素2在b內 訪問成功一次
------------------。。。。 以此類推
--------------最後3 1 2 最後一個元素又從存儲單元里訪問到一次 所以2/11

fifo+lru：同上加上最近雖少使用。列出上面的表格按隊列進入 把最長時間沒使用到的替換掉 一共訪問到2這個元素3次 所以就是3/11

『伍』 FIFO和LRU置換演算法的問題

FIFO 先進先出
-------------
剛開始內存為空 null, null, null
使用2，缺頁讀入 2, null, null
使用3，缺頁讀入 2, 3, null
使用2，直接使用 2, 3, null
使用1，缺頁讀入 2, 3, 1
使用5，缺頁讀入 3, 1, 5 因為2是最先讀入的，所以就把它刪掉
使用2，缺頁讀入 1, 5, 2
使用4，缺頁讀入 5, 2, 4
使用5，直接使用 5, 2, 4
使用3，缺頁讀入 2, 4, 3
使用2，直接使用 2, 4, 3
使用5，缺頁讀入 4, 3, 5
使用2，缺頁讀入 3, 5, 2

共9次缺頁
========================

LRU 會刪除最不常訪問的
----------------------
剛開始內存為空 null, null, null
使用2，缺頁讀入 2, null, null
使用3，缺頁讀入 3, 2, null
使用2，直接使用 2, 3, null
使用1，缺頁讀入 1, 2, 3
使用5，缺頁讀入 5, 1, 2 因為最近1和2都訪問過而3是很早之前用過的，所以就把它刪掉
使用2，直接使用 2, 5, 1
使用4，缺頁讀入 4, 2, 5
使用5，直接使用 5, 4, 2
使用3，缺頁讀入 3, 5, 4
使用2，缺頁讀入 2, 3, 5
使用5，直接使用 5, 2, 3
使用2，直接使用 2, 5, 3

共7次缺頁

『陸』 虛擬存儲器採用的頁面調度演算法是「先進先出」（FIFO）演算法嗎

虛擬存儲器採用的頁面調度演算法是「先進先出」（FIFO）演算法嗎。常見的替換演算法有4種。

①隨機演算法：用軟體或硬體隨機數產生器確定替換的頁面。

②先進先出：先調入主存的頁面先替換。

③近期最少使用演算法（LRU，Least Recently Used）：替換最長時間不用的頁面。

④最優演算法：替換最長時間以後才使用的頁面。這是理想化的演算法，只能作為衡量其他各種演算法優劣的標准。

虛擬存儲器的效率是系統性能評價的重要內容，它與主存容量、頁面大小、命中率，程序局部性和替換演算法等因素有關。

(6)fifo替換演算法擴展閱讀

虛擬存儲器地址變換基本上有3種形虛擬存儲器工作過程式：全聯想變換、直接變換和組聯想變換。任何邏輯空間頁面能夠變換到物理空間任何頁面位置的方式稱為全聯想變換。每個邏輯空間頁面只能變換到物理空間一個特定頁面的方式稱為直接變換。

組聯想變換是指各組之間是直接變換，而組內各頁間則是全聯想變換。替換規則用來確定替換主存中哪一部分，以便騰空部分主存，存放來自輔存要調入的那部分內容。

在段式虛擬存儲系統中，虛擬地址由段號和段內地址組成，虛擬地址到實存地址的變換通過段表來實現。每個程序設置一個段表，段表的每一個表項對應一個段，每個表項至少包括三個欄位：有效位(指明該段是否已經調入主存)、段起址(該段在實存中的首地址)和段長(記錄該段的實際長度)。

『柒』 FIFO演算法的解釋

/*我知道FIFO演算法的原理，可還是不理解這代碼，哪位高手指教下各個程序段的意思啊？不勝感激！ */
#include <stdio.h>
#include <stdlib.h>
#define mSIZE 3//分配三個內存頁框
#define pSIZE 12//總共12個進程
static int memery[mSIZE] = {0};
static int process[pSIZE] = {1,2,3,4,1,2,5,1,2,3,4,5};//頁面訪問序列
void FIFO();
int main()
{
get();
printf("\n(FIFO)\tcount\n");
FIFO();
system("PAUSE");
return 0;
}

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 FIFO()
{
int time[mSIZE] = {0}; //分配的三個頁框初始化為0
int i = 0, j = 0;
int m = -1, n = -1;
int max = -1,maxtime = 0;
int count = 0;

for(i = 0; i<pSIZE; i++) //開始循環，在頁框中尋找所需資源
{

for(j=0; j<mSIZE; j++) //判斷頁框中是否滿
{
if(memery[j] == 0) //尋找空頁框，並且記錄頁號
{
m = j;
break;
}
}

for(j = 0; j < mSIZE; j++)
{
if(memery[j] == process[i]) //判斷頁框中是否有進程所需訪問的資源
{
n = j;
}
}

for(j = 0; j < mSIZE;j++) //記錄在頁框中存放最長時間的資源，即第一個進入的資源
{
if(time[j]>maxtime)
{
maxtime = time[j]; //將存放最長時間資源的計數器的值賦給maxtime
max = j;
}
}

if(n == -1) //由於沒有在頁框中找到所需資源，並且也表已滿，發生缺頁中斷。
{
if(m != -1)
{
memery[m] = process[i]; //沒有替換的資源，則它對應的計數器加一
time[m] = 0;
for(j = 0;j <= m; j++)
{
time[j]++;
}
m = -1;
}
else
{
memery[max] = process[i]; //發生缺頁中斷，從前面的標記中尋找第一個進入頁表的資源替換
time[max] = 0; //替換後原來的最長則清0，
for(j = 0;j < mSIZE; j++)
{
time[j]++; //替換後，此資源對應的計數器加一
}
max = -1;
maxtime = 0;
count++;
}
}
else
{
memery[n] = process[i];
for(j = 0;j < mSIZE; j++) //一次分配對所有在頁表中的資源的計數器加一
{
time[j]++;
}
n = -1;
}
for(j = 0 ;j < mSIZE; j++)
{
printf("%d ",memery[j]); //輸出此次資源訪問時頁表中資源的情況。
}
printf("\t%d\n",count);
}
}

『捌』 如何用java實現fifo頁面置換演算法

[fifo.rar] - 操作系統中內存頁面的先進先出的替換演算法fifo
[先進先出頁面演算法程序.rar] - 分別實現最佳置換演算法(optimal)、先進先出(fifo)頁面置換演算法和最近最久未使用（LRU）置換演算法，並給出各演算法缺頁次數和缺頁率。
[0022.rar] - 模擬分頁式虛擬存儲管理中硬體的地址轉換和缺頁中斷，以及選擇頁面調度演算法處理缺頁中斷
[Change.rar] - 用java實現操作系統的頁面置換 其中包括 最佳置換演算法(Optimal)、先進先出演算法（First-in, First-out） 、最近最久不用的頁面置換演算法（LeastRecently Used Replacement）三種演算法的實現
[M_Management.rar] - 操作系統中內存管理頁面置換演算法的模擬程序，採用的是LRU置換演算法
[detail_of_44b0x_TCPIP.rar] - TCPIP 程序包載入到44b0x 的ADS1.2工程文件的說明書。說名了載入過程的細節和如何處理演示程序和代碼。演示代碼已經上傳，大家可以搜索
[.rar] - java操作系統頁面置換演算法： （1）進先出的演算法（fifo） （2）最近最少使用的演算法（LRU） （3）最佳淘汰演算法(OPT) （4）最少訪問頁面演算法(LFU) （註：由本人改成改進型Clock演算法） （5）最近最不經常使用演算法(NUR)

『玖』 FIFO頁面置換演算法到底是怎麼算的呀，先進先出是怎麼個先進先出下面這圖是怎麼算的，這個差又是怎麼

fifo就是先進先出，可以想像成隊列
lru是最久未使用，當需要替換頁面的時候，向前面看，最久沒使用的那個被替換
opt是替換頁面的時候，優先替換後面最遲出現的。
不懂再問。。