電子發燒友App
C語言是一門通用計算機編程語言，應用廣泛。C語言的設計目標是提供一種能以簡易的方式編譯、處理低級存儲器、產生少量的機器碼以及不需要任何運行環境支持便能運行的編程語言。
盡管C語言提供了許多低級處理的功能，但仍然保持著良好跨平臺的特性，以一個標準規格寫出的C語言程序可在許多電腦平臺上進行編譯，甚至包含一些嵌入式處理器（單片機或稱MCU）以及超級電腦等作業平臺。
二十世紀八十年代，為了避免各開發廠商用的C語言語法產生差異，由美國國家標準局為C語言制定了一套完整的國際標準語法，稱為ANSI C，作為C語言最初的標準。
First Input First Output的縮寫，先入先出隊列，這是一種傳統的按序執行方法，先進入的指令先完成并引退，跟著才執行第二條指令。
FIFO（First Input First Output），即先進先出隊列。在超市購物之后會提著我們滿滿的購物車來到收銀臺排在結賬隊伍的最后，眼睜睜地看著前面的客戶一個個離開。這就是一種先進先出機制，先排隊的客戶先行結賬離開。
c語言實現fifo算法及代碼
在操作系統中，當程序在運行過程中，若其所要訪問的頁面不再內存中而需要把他們調入內存，但內存已無空閑空間時，為了保證該進程能正常運行，系統必須從內存調出一頁程序或數據送磁盤的兌換區中。但哪一個頁面調出，須根據一定的算法確定。通常，把選擇換出頁面的算法稱為頁面置換算法（Page-Replacement Algorithms）。置換算法的好壞將直接影響到系統的性能。
1） 先進先出（FIFO）頁面置換算法
該算法總是淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰。該算法實現簡單，只需把一個進程調入內存，按先后順序排成一個隊列，并設置一個指針，稱為替換指針，使他總能指向最老的頁面。但該算法與進程與實際運行的規律不相適應，效率最差。
2） 最近最久為使用（LRU）算法
LRU算法是根據頁面調入內存后的使用情況進行決策的。就是利用“最近的過去”作為“最近的將來”的近似，因此是將最近最久未使用的頁面予以淘汰。該算法賦予每一個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經歷的時間t，當淘汰一個頁面時，選擇現有頁面中t值最大的，及最近最久為使用的頁面予以淘汰。
167#include 《stdio.h》
#define PAGES 12 /*頁面引用頁數*/
#define M 3 /*當前分配給改作業的物理塊數*/
//#define M 4
/*頁面引用串*/
int page［PAGES］ = {4，3，2，1，4，3，5，4，3，2，1，5};
int rel［M］［PAGES］; /*存儲結果數組*/
/*內存物理塊結構體*/
typedef struct{
int pnum; /*該塊中所存的頁面號*/
int tm; /*從最近一次調入所經歷的時間*/
}PBlock;
/*初始化物理塊數組*/
void init（PBlock *pb）
{
int i，j;
//pb = （PBlock*）malloc（sizeof（PBlock）*M）;
for（i=0;i《M;i++）{
pb［i］.pnum = -1;
pb［i］.tm = -1;
for（j=0;j《PAGES;j++）{
rel［i］［j］ = -1;
}
}
}
/*打印結果數組*/
void printRelArr（int rel［M］［PAGES］）
{
int i，j;
for（i=0;i《M;i++）{
for（j=0;j《PAGES;j++）{
if（rel［i］［j］==-1）
printf（“_ ”）;
else
printf（“%d ”，rel［i］［j］）;
}
printf（“\n”）;
}
}
/*打印一維數組*/
void printArr1（int *arr，int n）
{
int i;
for（i=0;i《n;i++）{
printf（“%d ”，arr［i］）;
}
printf（“\n”）;
}
/*查看頁面號為num的頁面是否在內存塊中，存在返回1*/
int in_mem（int num，PBlock *pb，int m）
{
int i;
int b = 0;
for（i=0;i《m;i++）{
if（pb［i］.pnum == num）{
b = 1;
break;
}
}
return b;
}
/*FIFO 算法的實現，無需考慮時間*/
int fifo（PBlock *pb，int m）
{
int lps=0; /*缺頁次數*/
double lpp; /*缺頁率*/
int p = 0; /*替換指針*/
int index =0; /*頁面號索引*/
while（index《PAGES）{
if（！in_mem（page［index］，pb，M））{ //如果該頁面不在物理塊中
pb［p］.pnum = page［index］; /*將該頁面放入物理塊中*/
p = （p+1）%M; /*替換指針移動*/
lps++; /*卻也次數加 1*/
for（int i=0;i《M;i++）{
rel［i］［index］ = pb［i］.pnum;
}
}
index++;
}
printf（“FIFO算法所得缺頁次數為 %d\n”，lps）;
lpp = （double）lps/PAGES;
printf（“FIFO算法缺頁率為 %0.4lf \n”，lpp）;
printf（“頁面號序列為：\n”）;
printArr1（page，PAGES）;
printf（“結果數列為：\n”）;
printRelArr（rel）;
return 0;
}
/*獲得最近最久的塊*/
int getP（PBlock *pb，int p）
{
int i;
bool out = true; //
for（i=0;i《M;i++）{
if（pb［i］.tm == -1）{
p = i;
out = false;
break;
}
}
if（out）{
for（i=0;i《M;i++）{
if（pb［i］.tm》pb［p］.tm）
p = i;
}
}
return p;
}
int getEQnum（int num，PBlock *pb）
{
int i;
int in = -1;
for（i=0;i《M;i++）{
if（pb［i］.pnum == num）{
in = i;
break;
}
}
return in;
}
/*LRU算法*/
void lru（PBlock *pb，int m）
{
int lps=0; /*缺頁次數*/
double lpp; /*缺頁率*/
int p = 0; /*替換指針*/
int index =0; /*頁面號索引*/
while（index《PAGES）{
if（！in_mem（page［index］，pb，m））{ /*如果頁面不在物理塊中*/
p = getP（pb，p）;
pb［p］.pnum = page［index］;
pb［p］.tm = 0;
lps++;
for（int i=0;i《M;i++）{
rel［i］［index］ = pb［i］.pnum;
}
}else{ /*如果頁面在物理塊中*/
int in = getEQnum（page［index］，pb）; /*獲取該頁面在物理塊中的索引*/
pb［in］.tm = 0;
}
int i;
for（i=0;i《M;i++）{
if（i！=p&&pb［i］.tm！=-1）{
pb［i］.tm++;
}
}
index++;
}
printf（“LRU算法所得缺頁次數為 %d \n”，lps）;
lpp = 1.0*lps/PAGES;
printf（“LRU算法缺頁率為： %0.4lf\n”，lpp）;
printf（“頁面號序列為：\n”）;
printArr1（page，PAGES）;
printf（“LRU結果數組為：\n”）;
printRelArr（rel）;
}
int main（）
{
//printArr（rel）;
PBlock pb［M］;
init（pb）;
fifo（pb，M）;
init（pb）;
lru（pb，M）;
return 0;
}
FIFO的C語言實現
/*-----------------FIFO算法-------------------*/ /*算法描述：淘汰最先進入物理塊的頁面*/ /* ---------writen by Xu Zhuozhuo----------*/
C++代碼示例：
#include 《iostream》
#define Num_Ref 20 //引用字符串的最大字符個數 using namespace std; int main（） {
int num_ref; //用戶的字符個數 int Phy_Blk［3］;
//物理塊個數為3 int ref_arr［Num_Ref］;
//存放用戶字符串
cout 《《“-----First In First Out-----” 《《endl 《《endl; do {
cout 《《“Please input the number of reference chars：” 《《endl; cin 》》num_ref;
//用戶的字符個數 }while（num_ref》Num_Ref）;
cout 《《“Please input the queue of reference chars：” 《《endl;
for（int i=0;i《num_ref;i++） //輸入引用字符串
cin 》》ref_arr［i］;
for（int j=0;j《3;j++） //物理塊數組初始化
Phy_Blk［j］=ref_arr［j］;
//FIFO，并輸出本次替換結果
cout 《《endl 《《“Display the replacement procedure： ”;
cout 《《endl 《《“---------------------------------- ” 《《endl;
for（int loop=3;loop《num_ref;loop++）
{
Phy_Blk［0］=Phy_Blk［1］;
Phy_Blk［1］=Phy_Blk［2］;
Phy_Blk［2］=ref_arr［loop］;
cout 《《endl 《《“［” 《《loop-2 《《“］。 Physical block array content： ”;
for（int inloop=0;inloop《3;inloop++）
cout 《《Phy_Blk［inloop］ 《《“ ”;
}
return 0;
}
工商網監
評論