fifo演算法

1. 關於先進先出（FIFO）頁面淘汰演算法

輸入：1，2，3，4，1，2，5，1，2，3，4，5

先進先出，就是保存最近3個訪問的記錄在內存中
, , <—1 中斷1次
, ,1<—2 中斷1次
, 1,2<—3 中斷1次
1,2,3 <—4 中斷1次
2,3,4 <—1 中斷1次
3,4 ,1<—2 中斷1次
4,1,2<—5 中斷1次
1,2,5<—1 命中，不中斷
2,5,1 <—2 命中，不中斷
5,1,2<—3 中斷1次
1,2,3 <—4 中斷1次
2,3,4 <—5 中斷1次
3,4,5

累計中斷12次

2. 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);
}
}

3. LRU和FIFO演算法計算缺頁次數(急)

沒分
LRU：9次

4. 先進先出置換演算法，（fifo）

的確是書錯了

5. 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;
}

6. 請大佬幫忙講解一下這個FIFO演算法和LRU演算法 跪求(T^T)

注意：

1. 書上的表示方法不能很好的表示LRU的思想，所以我們都採用上圖的畫圖方法

2. 對於前三個是否算做缺頁這個不同的教材有不同的說法，要具體看題目說明
   

7. 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次缺頁

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

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

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

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

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

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

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

(8)fifo演算法擴展閱讀

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

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

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

9. fifo演算法適用於什麼場合又有何缺點

適用於:按線性順序訪問的地址空間
缺點:可能抖動，會發生Belady異常

10. FIFO調度演算法和LRU演算法

FIFO：先進先出調度演算法
LRU：最近最久未使用調度演算法

兩者都是緩存調度演算法，經常用作內存的頁面置換演算法。

打一個比方，幫助你理解。

你有很多的書，比如說10000本。
由於你的書實在太多了，你只能放在地下室裡面。
你看書的時候不會在地下室看書，而是在書房看書。
每次，你想看書都必須跑到地下室去找出來你想看的書，
然後抱回來放到書桌上，之後才開始看。
還有就是，有一些書你會反復的看，今天看了也許過幾天又要看。
總之，你自己是不知道你哪天會需要看哪本書的。
你的老師每天下課的時候會給你布置一個書單，讓你晚上回去去看哪本書。
（假設你老師讓你看的書在你的地下室裡面都有）

跑地下室當然是非常麻煩的，所以你希望你的經常看的那些書最好放在書桌上。
但是你的書房的書桌同時只能擺放10本書（這個是假設的啊）。
那麼，問題來了。
到底把哪些說留在書桌上最好呢？
這里說的最好，就是說你盡量少的跑地下室去找書。

為了解決這個問題，人們發明了很多的演算法。
其中，比較常見的就是上面這兩種：FIFO演算法和LRU演算法。

FIFO演算法
很簡單，我把書桌上的10本書按照放置時間先後堆放成一堆。
這里的放置時間，就是說這本書在我的書桌上放了幾天了。
每次要看書的時候，我先在書桌上找，找到就直接可以讀了。
讀完之後放回原來的位置就可以，不打亂順序。
如果書桌上面沒有我要讀的書，就去地下室找。
找來之後，我就把書桌上放的時間最長的那本（也就是
書堆裡面最下面的那本書）放回地下室。
然後把我今天需要看的這本書放在書堆的最上面。

LRU演算法
也不難，我把書桌上的10本書按照閱讀時間先後堆放成一堆。
這里的閱讀時間，就是說我最近一次讀這本書是幾天之前。
每次要看書的時候，我先在書桌上找，找到就直接可以讀了。
讀完之後放在書堆的最上面。
如果書桌上面沒有我要讀的書，就去地下室找。
找來之後，我就把書桌上最久沒有閱讀的那本
（也就是書堆裡面最下面的那本書）放回地下室。
然後把我今天需要看的這本書放在書堆的最上面。

上面這個比方，相信你可以看明白吧。
這里的地下室對應內存，書桌對應緩存，書對應頁面。