C語言是一門通用計(jì)算機(jī)編程語言，應(yīng)用廣泛。C語言的設(shè)計(jì)目標(biāo)是提供一種能以簡(jiǎn)易的方式編譯、處理低級(jí)存儲(chǔ)器、產(chǎn)生少量的機(jī)器碼以及不需要任何運(yùn)行環(huán)境支持便能運(yùn)行的編程語言。

　　盡管C語言提供了許多低級(jí)處理的功能，但仍然保持著良好跨平臺(tái)的特性，以一個(gè)標(biāo)準(zhǔn)規(guī)格寫出的C語言程序可在許多電腦平臺(tái)上進(jìn)行編譯，甚至包含一些嵌入式處理器（單片機(jī)或稱MCU）以及超級(jí)電腦等作業(yè)平臺(tái)。

　　二十世紀(jì)八十年代，為了避免各開發(fā)廠商用的C語言語法產(chǎn)生差異，由美國國家標(biāo)準(zhǔn)局為C語言制定了一套完整的國際標(biāo)準(zhǔn)語法，稱為ANSI C，作為C語言最初的標(biāo)準(zhǔn)。

　　First Input First Output的縮寫，先入先出隊(duì)列，這是一種傳統(tǒng)的按序執(zhí)行方法，先進(jìn)入的指令先完成并引退，跟著才執(zhí)行第二條指令。

　　FIFO（First Input First Output），即先進(jìn)先出隊(duì)列。在超市購物之后會(huì)提著我們滿滿的購物車來到收銀臺(tái)排在結(jié)賬隊(duì)伍的最后，眼睜睜地看著前面的客戶一個(gè)個(gè)離開。這就是一種先進(jìn)先出機(jī)制，先排隊(duì)的客戶先行結(jié)賬離開。

　　c語言實(shí)現(xiàn)fifo算法及代碼

　　在操作系統(tǒng)中，當(dāng)程序在運(yùn)行過程中，若其所要訪問的頁面不再內(nèi)存中而需要把他們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時(shí)，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存調(diào)出一頁程序或數(shù)據(jù)送磁盤的兌換區(qū)中。但哪一個(gè)頁面調(diào)出，須根據(jù)一定的算法確定。通常，把選擇換出頁面的算法稱為頁面置換算法（Page-Replacement Algorithms）。置換算法的好壞將直接影響到系統(tǒng)的性能。

　　1） 先進(jìn)先出（FIFO）頁面置換算法

　　該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單，只需把一個(gè)進(jìn)程調(diào)入內(nèi)存，按先后順序排成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使他總能指向最老的頁面。但該算法與進(jìn)程與實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，效率最差。

　　2） 最近最久為使用（LRU）算法

　　LRU算法是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的。就是利用“最近的過去”作為“最近的將來”的近似，因此是將最近最久未使用的頁面予以淘汰。該算法賦予每一個(gè)頁面一個(gè)訪問字段，用來記錄一個(gè)頁面自上次被訪問以來所經(jīng)歷的時(shí)間t，當(dāng)淘汰一個(gè)頁面時(shí)，選擇現(xiàn)有頁面中t值最大的，及最近最久為使用的頁面予以淘汰。

　　167#include 《stdio.h》

　　#define PAGES 12 /*頁面引用頁數(shù)*/

　　#define M 3 /*當(dāng)前分配給改作業(yè)的物理塊數(shù)*/

　　//#define M 4

　　/*頁面引用串*/

　　int page［PAGES］ = {4，3，2，1，4，3，5，4，3，2，1，5};

　　int rel［M］［PAGES］; /*存儲(chǔ)結(jié)果數(shù)組*/

　　/*內(nèi)存物理塊結(jié)構(gòu)體*/

　　typedef struct{

　　int pnum; /*該塊中所存的頁面號(hào)*/

　　int tm; /*從最近一次調(diào)入所經(jīng)歷的時(shí)間*/

　　}PBlock;

　　/*初始化物理塊數(shù)組*/

　　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;

　　}

　　}

　　}

　　/*打印結(jié)果數(shù)組*/

　　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”）;

　　}

　　}

　　/*打印一維數(shù)組*/

　　void printArr1（int *arr，int n）

　　{

　　int i;

　　for（i=0;i《n;i++）{

　　printf（“%d ”，arr［i］）;

　　}

　　printf（“\n”）;

　　}

　　/*查看頁面號(hào)為num的頁面是否在內(nèi)存塊中，存在返回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 算法的實(shí)現(xiàn)，無需考慮時(shí)間*/

　　int fifo（PBlock *pb，int m）

　　{

　　int lps=0; /*缺頁次數(shù)*/

　　double lpp; /*缺頁率*/

　　int p = 0; /*替換指針*/

　　int index =0; /*頁面號(hào)索引*/

　　while（index《PAGES）{

　　if（！in_mem（page［index］，pb，M））{ //如果該頁面不在物理塊中

　　pb［p］.pnum = page［index］; /*將該頁面放入物理塊中*/

　　p = （p+1）%M; /*替換指針移動(dòng)*/

　　lps++; /*卻也次數(shù)加 1*/

　　for（int i=0;i《M;i++）{

　　rel［i］［index］ = pb［i］.pnum;

　　}

　　}

　　index++;

　　}

　　printf（“FIFO算法所得缺頁次數(shù)為 %d\n”，lps）;

　　lpp = （double）lps/PAGES;

　　printf（“FIFO算法缺頁率為 %0.4lf \n”，lpp）;

　　printf（“頁面號(hào)序列為：\n”）;

　　printArr1（page，PAGES）;

　　printf（“結(jié)果數(shù)列為：\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; /*缺頁次數(shù)*/

　　double lpp; /*缺頁率*/

　　int p = 0; /*替換指針*/

　　int index =0; /*頁面號(hào)索引*/

　　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算法所得缺頁次數(shù)為 %d \n”，lps）;

　　lpp = 1.0*lps/PAGES;

　　printf（“LRU算法缺頁率為： %0.4lf\n”，lpp）;

　　printf（“頁面號(hào)序列為：\n”）;

　　printArr1（page，PAGES）;

　　printf（“LRU結(jié)果數(shù)組為：\n”）;

　　printRelArr（rel）;

　　}

　　int main（）

　　{

　　//printArr（rel）;

　　PBlock pb［M］;

　　init（pb）;

　　fifo（pb，M）;

　　init（pb）;

　　lru（pb，M）;

　　return 0;

　　}

　　FIFO的C語言實(shí)現(xiàn)

　　/*-----------------FIFO算法-------------------*/ /*算法描述：淘汰最先進(jìn)入物理塊的頁面*/ /* ---------writen by Xu Zhuozhuo----------*/

　　C++代碼示例：

　　#include 《iostream》

　　#define Num_Ref 20 //引用字符串的最大字符個(gè)數(shù) using namespace std; int main（） {

　　int num_ref; //用戶的字符個(gè)數(shù) int Phy_Blk［3］;

　　//物理塊個(gè)數(shù)為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;

　　//用戶的字符個(gè)數(shù) }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++） //物理塊數(shù)組初始化

　　Phy_Blk［j］=ref_arr［j］;

　　//FIFO，并輸出本次替換結(jié)果

　　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;

　　}