當前位置:首頁 » 操作系統 » fifo演算法

fifo演算法

發布時間: 2022-01-09 10:26:00

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

Ⅱ 先進先出置換演算法,(fifo)

的確是書錯了

Ⅲ 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調度演算法和LRU演算法

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

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

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

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

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

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

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

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

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

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

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

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

沒分
LRU:9次

Ⅶ 如何用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)

Ⅷ hadoop集群中,fifo調度演算法具有哪些特點

首先介紹了Hadoop平台下作業的分布式運行機制,然後對Hadoop平台自帶的4種任務調度器做分析和比較,最後在分析JobTracker類文件的基礎上指出了創建自定義任務調度器所需完成的工作。首先Hadoop集群式基於單伺服器的,只有一個伺服器節點負責調度整個集群的作業運行,主要的具體工作是切分大數據量的作業,指定哪些Worker節點做Map工作、哪些Worker節點做Rece工作、與Worker節點通信並接受其心跳信號、作為用戶的訪問入口等等。其次,集群中的每個Worker節點相當於一個器官,運行著主節點所指派的具體作業。這些節點會被分為兩種類型,一種是接收分塊之後的作業並做映射工作。另一種是負責把前面所做的映射工作按照約定的規則做一個統計。Task-Tracker通過運行一個簡單循環來定期地發送心跳信號(heartbeat)給JobTracker.這個心跳信號會把TaskTracker是否還在存活告知JobTracker,TaskTracker通過信號指明自己是否已經准備好運行新的任務.一旦TaskTracker已經准備好接受任務,JobTracker就會從作業優先順序表中選定一個作業並分配下去.至於到底是執行Map任務還是Rece任務,是由TaskTracker的任務槽所決定的.默認的任務調度器在處理Rece任務之前,會優先填滿空閑的Map任務槽.因此,如果TaskTracker滿足存在至少一個空閑任務槽時,JobTracker會為它分配Map任務,否則為它選擇一個Rece任務.TaskTracker在運行任務的時候,第一步是從共享文件系統中把作業的JAR文件復制過來,從而實現任務文件的本地化.第二步是TaskTracker為任務新建一個本地文件夾並把作業文件解壓在此目錄中.第三步是由Task-Tracker新建一個TaskRunner實例來運行該任務.Hadoop平台默認的調度方案就是JobQueueTaskScheler,這是一種按照任務到來的時間先後順序而執行的調度策略.這種方式比較簡單,JobTracker作為主控節點,僅僅是依照作業到來的先後順序而選擇將要執行的作業.當然,這有一定的缺陷,由於Hadoop平台是默認將作業運行在整個集群上的,那麼如果一個耗時非常大的作業進入執行期,將會導致其餘大量作業長時間得不到運行.這種長時間運行的優先順序別並不高的作業帶來了嚴重的作業阻塞,使得整個平台的運行效率處在較低的水平.Hadoop平台對這種FIFO(FirstINAndFirstOut)機制所給出的解決法是調用SetJobPriority()方法,通過設置作業的權重級別來做平衡調度.FairScheler是一種「公平」調度器,它的目標是讓每個用戶能夠公平地共享Hadoop集群計算能力.當只有一個作業運行的時候,它會得到整個集群的資源.隨著提交到作業表中作業的增多,Hadoop平台會把集群中空閑出來的時間槽公平分配給每個需要執行的作業.這樣即便其中某些作業需要較長時間運行,平台仍然有能力讓那些短作業在合理時間內完成[3].FairScheler支持資源搶占,當一個資源池在一定時段內沒有得到公平共享時,它會終止該資源池所獲得的過多的資源,同時把這些釋放的資源讓給那些資源不足的資源池.Hadoop平台中的CapacityScheler是由Yahoo貢獻的,在調度器上,設置了三種粒度的對象:queue,job,task.在該策略下,平台可以有多個作業隊列,每個作業隊列經提交後,都會獲得一定數量的TaskTracker資源.具體調度流程如下.(1)選擇queue,根據資源庫的使用情況從小到大排序,直到找到一個合適的job.(2)選擇job,在當前所選定的queue中,按照作業提交的時間先後以及作業的權重優先順序別進行排序,選擇合適的job.當然,在job選擇時還需要考慮所選作業是否超出目前現有的資源上限,以及資源池中的內存是否夠該job的task用等因素.(3)選擇task,根據本地節點的資源使用情況來選擇合適的task.雖然Hadoop平台自帶了幾種調度器,但是上述3種調度方案很難滿足公司復雜的應用需求.因此作為平台的個性化使用者,往往需要開發自己的調度器.Hadoop的調度器是在JobTracker中載入和調用的,因此開發一個自定義的調度器就必須搞清楚JobTracker類文件的內部機制.作為Hadoop平台的核心組件,JobTracker監控著整個集群的作業運行情況並對資源進行管理調度.每個Task-Tracker每隔3s通過heartbeat向JobTracker匯報自己管理的機器的一些基本信息,包括內存使用量、內存的剩餘量以及空閑的slot數目等等[5].一旦JobTracker發現了空閑slot,便會調用調度器中的AssignTask方法為該TaskTracker分配task。

Ⅸ 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演算法和LRU演算法 跪求(T^T)

注意:

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

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

熱點內容
java喂狗 發布:2024-03-29 10:03:33 瀏覽:546
mcafee按訪問掃描 發布:2024-03-29 10:02:40 瀏覽:816
編譯成debug版本 發布:2024-03-29 09:06:55 瀏覽:884
wms伺服器地址 發布:2024-03-29 09:05:55 瀏覽:415
mep編程器 發布:2024-03-29 09:05:13 瀏覽:139
大小s我們一家訪問人 發布:2024-03-29 09:03:16 瀏覽:532
造物者編程 發布:2024-03-29 08:50:27 瀏覽:534
sql技能 發布:2024-03-29 08:50:23 瀏覽:56
希沃安卓下載安裝應用在哪裡 發布:2024-03-29 08:22:51 瀏覽:631
python和excel 發布:2024-03-29 07:47:03 瀏覽:861