求一个操作系统页面置换算法先进先出的实验报告 操作系统题：页面置换算法 OPT FIFO LRU
\u9875\u9762\u7f6e\u6362\u7b97\u6cd5\u7684\u5b9e\u9a8c#include
#include
#include
#include
#define total_instruction 200 /*\u6307\u4ee4\u6d41\u957f*/
#define M 16 /*\u5b9e\u9645\u9875\u6570*/
#define N 4 //\u53ef\u7528\u9875\u9762\u6570
struct Pro
{
int num,time;
};
int a[total_instruction];
int page[N];
void Input(Pro p[total_instruction])
{
int m,i,m1,m2;
srand( (unsigned int )time(NULL));
m=rand( )%160; //
for(i=0;i<total_instruction;) /*\u4ea7\u751f\u6307\u4ee4\u961f\u5217*/
{
if(m159)
{
printf("When i==%d,Error,m==%d\n",i,m);
exit(0);
}
a[i]=m; /*\u4efb\u9009\u4e00\u6307\u4ee4\u8bbf\u95ee\u70b9m*/
a[i+1]=a[i]+1;
a[i+2]=a[i]+2; /*\u987a\u5e8f\u6267\u884c\u4e24\u6761\u6307\u4ee4*/
int m1=rand( )%m; /*\u6267\u884c\u524d\u5730\u5740\u6307\u4ee4m1 */
a[i+3]=m1;
a[i+4]=m1+1;
a[i+5]=m1 + 2;/*\u987a\u5e8f\u6267\u884c\u4e24\u6761\u6307\u4ee4*/
// s=(158-a[i+5])*rand( )/32767/32767/2+a[i+5]+2;
m2 = rand()%(157-m1)+m1+3;
a[i+6]=m2;
if( (m2+2) > 159 )
{
a[i+7] = m2+1;
i +=8;
}
else
{
a[i+7] = m2+1;
a[i+8] = m2+2;
i = i+9;
}
m = rand()%m2;
}
for (i=0;i<total_instruction;i++) /*\u5c06\u6307\u4ee4\u5e8f\u5217\u53d8\u6362\u6210\u9875\u5730\u5740\u6d41*/
{
p[i].num=a[i]/10;
p[i].time = 0;
}
}
void print(Pro *page1)//\u6253\u5370\u5f53\u524d\u7684\u9875\u9762
{
Pro *page=new Pro[N];
page=page1;
for(int i=0;i<N;i++)
cout<<page[i].num<<" ";
cout<<endl;
}
int Search(int e,Pro *page1 )
{
Pro *page=new Pro[N];
page=page1;
for(int i=0;i<N;i++)if(e==page[i].num)return i;
return -1;
}
int Max(Pro *page1)
{
Pro *page=new Pro[N];
page=page1;
int e=page[0].time,i=0;
while(i<N)//\u627e\u51fa\u79bb\u73b0\u5728\u65f6\u95f4\u6700\u957f\u7684\u9875\u9762
{
if(e<page[i].time)e=page[i].time;
i++;
}
for( i=0;i<N;i++)if(e==page[i].time)return i;
return -1;
}
int Compfu(Pro *page1,int i,int t,Pro p[M])
{
Pro *page=new Pro[N];
page=page1;
int count=0;
for(int j=i;j<M;j++)
{
if(page[t].num==p[j].num )break;
else count++;
}
return count;
}
int main()
{
Pro p[total_instruction];
Pro *page=new Pro[N];
char c;
int t=0;
float n=0;
Input(p);
do{
for(int i=0;i<N;i++)//\u521d\u8bd5\u5316\u9875\u9762\u57fa\u672c\u60c5\u51b5
{
page[i].num=0;
page[i].time=2-i;
}
i=0;
cout<<"f:FIFO\u9875\u9762\u7f6e\u6362"<<endl;
cout<<"l:LRU\u9875\u9762\u7f6e\u6362"<<endl;
cout<<"o:OPT\u9875\u9762\u7f6e\u6362"<<endl;
cout<<"\u6309\u5176\u5b83\u952e\u7ed3\u675f"<<endl;
cin>>c;
if(c=='f')//FIFO\u9875\u9762\u7f6e\u6362
{
n=0;
cout<<"\u9875\u9762\u7f6e\u6362\u60c5\u51b5: "<<endl;
while( i< total_instruction)
{
if(Search(p[i].num,page)>=0)
i++;//\u627e\u5230\u76f8\u540c\u7684\u9875\u9762
else
{
if(t==N)t=0;
else
{
n++;//
page[t].num=p[i].num;
print(page);
t++;
}
}
}
cout<<"\u7f3a\u9875\u6b21\u6570\uff1a"<<n<<" \u7f3a\u9875\u7387\uff1a"<<n/total_instruction<<endl;
}
if(c=='l')//LRU\u9875\u9762\u7f6e\u6362
{
n=0;
cout<<"\u9875\u9762\u7f6e\u6362\u60c5\u51b5: "<<endl;
while(i<total_instruction)
{
int k;
k=t=Search(p[i].num,page);
if(t>=0)
page[t].time=0;
else
{
n++;
t=Max(page);
page[t].num=p[i].num;
page[t].time=0;
}
if(t==0){page[t+1].time++;page[t+2].time++;}
if(t==1){page[2].time++;page[0].time++;}
if(t==2){page[1].time++;page[0].time++;}
if(k==-1) print(page);
i++;
}
cout<<"\u7f3a\u9875\u6b21\u6570\uff1a"<<n<<" \u7f3a\u9875\u7387\uff1a"<<n/total_instruction<<endl;
}
if(c=='o')//OPT\u9875\u9762\u7f6e\u6362
{
n=0;
while(i<total_instruction)
{
if(Search(p[i].num,page)>=0)i++;
else
{
int temp=0,cn;
for(t=0;t<N;t++)
{
if(temp<Compfu(page,i,t,p))
{
temp=Compfu(page,i,t,p);
cn=t;
}
}
page[cn]=p[i];
n++;
print(page);
i++;
}
}
cout<<"\u7f3a\u9875\u6b21\u6570\uff1a"<<n<<" \u7f3a\u9875\u7387\uff1a"<<n/total_instruction<<endl;
}
}while(c=='f'||c=='l'||c=='o');
return 0;
}
fifo\u5c31\u662f\u5148\u8fdb\u5148\u51fa\uff0c\u53ef\u4ee5\u60f3\u8c61\u6210\u961f\u5217
lru\u662f\u6700\u4e45\u672a\u4f7f\u7528\uff0c\u5f53\u9700\u8981\u66ff\u6362\u9875\u9762\u7684\u65f6\u5019\uff0c\u5411\u524d\u9762\u770b\uff0c\u6700\u4e45\u6ca1\u4f7f\u7528\u7684\u90a3\u4e2a\u88ab\u66ff\u6362
opt\u662f\u66ff\u6362\u9875\u9762\u7684\u65f6\u5019\uff0c\u4f18\u5148\u66ff\u6362\u540e\u9762\u6700\u8fdf\u51fa\u73b0\u7684\u3002
\u4e0d\u61c2\u518d\u95ee\u3002\u3002
1.B 2.c 3。 D 4B 5B
二填空
1，最优；先进先出；最近最久未使用
2. 13；15；
3. 123456721；123567421
4.段；段；页；页；三；二
三，问答
1.答：三个页面的物理起始地址分别是：4k,6K,12K,
2500= 2K+452,所以在第二个逻辑页面6K的起始地址，实际地址是6K+452；
2.LRU：装入顺序：2 3 1 5 4 3 2
换出顺序： 3 1 2 4 缺页次数7次
FIFO：装入顺序：2 3 1 5 2 4 3 5 2
换出顺序： 2 3 1 5 2 4 缺页次数9次
时钟：装入顺序：2 3 1 5 2 4 3 2
换出顺序： 2 3 1 2 4 缺页次数8次
时钟算法性能处于中间，优于FiFo，差于LRU，但由于LRU算法的硬件实现比较麻烦，所以时钟算法问兼顾了效率和硬件实现
绛旓細1锛屾渶浼橈紱鍏堣繘鍏堝嚭锛涙渶杩戞渶涔呮湭浣跨敤 2. 13锛15锛3. 123456721锛123567421 4.娈碉紱娈碉紱椤碉紱椤碉紱涓夛紱浜 涓夛紝闂瓟 1.绛旓細涓涓〉闈鐨勭墿鐞嗚捣濮嬪湴鍧鍒嗗埆鏄細4k,6K,12K,2500= 2K+452,鎵浠ュ湪绗簩涓昏緫椤甸潰6K鐨勮捣濮嬪湴鍧锛屽疄闄呭湴鍧鏄6K+452锛2.LRU锛氳鍏ラ『搴忥細2 3 1 5 4 3 2...
绛旓細鍏堣繘鍏堝嚭FIFO锛氾紙0浠ｈ〃鏈鍗犵敤锛夛紙1锛1锛0锛0锛0锛2锛1锛2锛0锛0锛3锛1锛2锛3锛0锛4锛1锛2锛3锛4锛5锛1锛2锛3锛4璁块棶2锛6锛1锛2锛3锛4璁块棶1锛7锛5锛2锛3锛4璁块棶5鏇挎崲1锛8锛5锛6锛3锛4璁块棶6鏇挎崲2锛9锛5锛6锛2锛4璁块棶2鏇挎崲3锛10锛5锛6锛2锛1璁块棶1鏇挎崲4锛11锛5锛6...
绛旓細1. 鍏堣繘鍏堝嚭锛團IFO锛夌畻娉曪細杩欐槸鏈绠鍗曠殑椤甸潰缃崲绠楁硶锛屽畠鎸夌収椤甸潰杩涘叆鍐呭瓨鐨勯『搴忥紝渚濇灏嗘渶涔呮病鐢ㄨ繃鐨勯〉闈㈡窐姹板嚭鍘汇傝繖绉嶇畻娉曠殑浼樼偣鏄疄鐜扮畝鍗曪紝缂虹偣鏄湪鏌愪簺鎯呭喌涓嬭〃鐜颁笉浣筹紝灏ゅ叾鏄綋绋嬪簭鐨勮繍琛岃矾寰勯潪甯歌鏁存椂銆2. 鏈杩戞渶涓嶇粡甯镐娇鐢紙LRU锛夌畻娉曪細LRU绠楁硶鏄渶甯哥敤鐨勯〉闈㈢疆鎹㈢畻娉曚箣涓锛屽畠鏍规嵁椤甸潰鐨勪娇鐢ㄥ巻...
绛旓細fifo灏辨槸鍏堣繘鍏鍑猴紝鍙互鎯宠薄鎴愰槦鍒 lru鏄渶涔呮湭浣跨敤锛屽綋闇瑕佹浛鎹椤甸潰鐨勬椂鍊欙紝鍚戝墠闈㈢湅锛屾渶涔呮病浣跨敤鐨勯偅涓鏇挎崲 opt鏄浛鎹㈤〉闈㈢殑鏃跺欙紝浼樺厛鏇挎崲鍚庨潰鏈杩熷嚭鐜扮殑銆備笉鎳傚啀闂傘
绛旓細2銆佺畻娉曡鍒欙細灏嗘墍鏈夊彲鑳借缃崲鐨勯〉闈㈡帓鎴愪竴涓惊鐜槦鍒楋紙璁块棶浣嶏紝淇敼浣嶏級绗竴杞細浠庡綋鍓嶄綅缃紑濮嬫壂鎻忓埌绗竴涓紙0锛0锛夌殑椤电敤浜庢浛鎹3銆佺墿鐞嗛〉甯ф暟閲忎负4锛屼笖鍒濆鏃舵病鏈夊搴旂殑铏氭嫙椤点4銆乴ru绠楁硶鏄竴绉椤甸潰缃崲绠楁硶锛屽湪瀵逛簬鍐呭瓨涓絾鏄張涓嶇敤鐨勬暟鎹潡锛屽彨鍋歀RU锛鎿嶄綔绯荤粺浼氭牴鎹偅浜涙暟鎹睘浜嶭RU鑰屽皢鍏...
绛旓細鏈绠鍗曠殑椤甸潰缃崲绠楁硶鏄厛鍏ュ厛鍑猴紙FIFO锛夋硶銆傝繖绉嶇畻娉曠殑瀹炶川鏄紝鎬绘槸閫夋嫨鍦ㄤ富瀛樹腑鍋滅暀鏃堕棿鏈闀匡紙鍗虫渶鑰侊級鐨勪竴椤电疆鎹紝鍗鍏堣繘鍏ュ唴瀛樼殑椤碉紝鍏堥鍑哄唴瀛樸傚父瑙佺殑椤甸潰缃崲绠楁硶鏈塅IFO銆丩RU绛夈傚瀛樺拰鍐呭瓨涔嬮棿鐨勬暟鎹紶杈擄細褰撳彂鐢熺己椤典腑鏂渶瑕佸皢鏌愪釜椤甸潰浠庡瀛樿皟鍏ュ唴瀛樻椂锛岄渶瑕佽繘琛屽ぇ閲忔暟鎹紶杈撱備负浜嗘彁楂樻晥鐜囷紝...
绛旓細 涓句緥璇存槑锛屽姞鍏ユ煇绯荤粺涓烘煇杩涚▼鍒嗛厤浜嗗洓涓唴瀛樺潡锛屽苟鑰冭檻鍒版湁浠ヤ笅椤甸潰鍙峰紩鐢ㄤ覆锛1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7 杩欓噷鍏堢洿鎺ョ粰鍑虹瓟妗 缁撴灉鍥 鏈浣缃崲绠楁硶閭ｆц兘鏈濂斤紝浣嗘棤娉曞疄鐜般鍏堣繘鍏堝嚭缃崲绠楁硶瀹炵幇绠鍗...
绛旓細椤甸潰缃崲绠楁硶涔婰RU绠楁硶1銆乴ru绠楁硶鏄竴绉嶉〉闈㈢疆鎹㈢畻娉曪紝鍦ㄥ浜庡唴瀛樹腑浣嗘槸鍙堜笉鐢ㄧ殑鏁版嵁鍧楋紝鍙仛LRU锛鎿嶄綔绯荤粺浼氭牴鎹偅浜涙暟鎹睘浜嶭RU鑰屽皢鍏剁Щ鍑哄唴瀛樿岃吘鍑虹┖闂存潵鍔犺浇鍙﹀鐨勬暟鎹2銆佽繖灏辨槸LRU绠楁硶鐨勫叏閮ㄥ唴瀹广備竴绉峀RU杩戜技绠楁硶鏄渶杩戞湭浣跨敤绠楁硶銆傚畠鍦ㄥ瓨鍌ㄥ垎鍧楄〃鐨勬瘡涓琛ㄩ」涓鍔犱竴涓紩鐢ㄤ綅锛屾搷浣滅郴缁熷畾鏈熷湴...
绛旓細1銆鍏堣繘鍏堝嚭锛團IFO锛夌畻娉 杩欐槸鏈绠鍗曠殑椤甸潰缃崲绠楁硶銆傚畠閫氳繃缁存姢涓涓〉闈㈤槦鍒楋紝灏嗘渶鏃╄繘鍏ュ唴瀛樼殑椤甸潰缃崲鍑哄幓銆傚綋涓涓柊鐨勯〉闈㈤渶瑕佽繘鍏ュ唴瀛樻椂锛屼細灏嗘渶鏃╄繘鍏ュ唴瀛樼殑椤甸潰缃崲鍑哄幓銆侳IFO绠楁硶鐨勪紭鐐规槸瀹炵幇绠鍗曪紝浣嗗畠娌℃湁鑰冭檻椤甸潰鐨勮闂鐜囧拰閲嶈鎬э紝鍙兘浼氬鑷存ц兘浣庝笅銆2銆佹渶杩戞渶涔呮湭浣跨敤锛圠RU锛夌畻娉 LRU...
绛旓細瑙ｏ細鏍规嵁鎵缁欓〉闈㈣蛋鍚戯紝閲囩敤FIFO娣樻卑绠楁硶鐨勯〉闈㈢疆鎹㈡儏鍐靛涓嬶細杩欓噷鐨勯〉闈㈣蛋鍚戯紝鍗充负绯荤粺瑕佽皟鐢ㄧ殑椤靛彿銆傚湪璇锋眰鍒嗛〉绯荤粺涓紝鍙互閫氳繃鏌ヨ椤佃〃涓殑鐘舵佷綅鏉ョ‘瀹氭墍瑕佽闂殑椤甸潰鏄惁瀛樺湪浜庡唴瀛樹腑銆傜浜屾鏈轰細绠楁硶锛氫笌FIFO銆丱PT銆丩RU銆丯RU绛夊悓涓鎿嶄綔绯荤粺涓姹傚垎椤靛紡绠＄悊鏂瑰紡鐨椤甸潰缃崲绠楁硶銆傜浜屾鏈轰細绠楁硶鐨勫熀鏈...
