c語言頁面置換演算法
//熬夜弄出來的，記得加分哦
#include<stdio.h>
void Print(int bc[],int blockCount)
{
for(int i=0;i<blockCount;i++)
{
printf("%d ",bc[i]);
}
printf("\n");
}
bool Travel(int bc[],int blockCount,int x)
{
bool is_found=false;
int i;
for(i=0;i<blockCount;i++)
{
if(bc[i]==x)
{
is_found=true;
break;
}
}
return is_found;
}
void FIFO(int pc[],int bc[],int pageCount,int blockCount)
{
printf("0：FIFO置換演算法\n");
int i;
if(pageCount<=blockCount)
{
printf("缺頁次數為0\n");
printf("缺頁率為0\n");
}
else
{
int noPage=0;
int p=0;
for(i=0;i<pageCount;i++)
{
//printf("引用頁：%d\n",pc[i]);
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i];
}
else
{
if(p==blockCount)
{
p=0;
}
bc[p]=pc[i];
p++;
}
noPage++;
//printf("物理塊情況：\n");
//Print(bc,blockCount);
}
//printf("\n");
}
printf("FIFO缺頁次數為:%d\n",noPage);
printf("FIFO缺頁率為:%.2f%%\n",(float)noPage/pageCount*100);
}
}
int FoundMaxNum(int a[],int n)
{
int k,j;
k=a[0];
j=0;
for (int i=0;i<n;i++)
{
if(a[i]>=k)
{
k=a[i];
j=i;
}
}
return j;
}
void LRU(int pc[],int bc[],int pageCount,int blockCount)
{
printf("1：LRU置換演算法\n");
if(pageCount<=blockCount)
{
printf("缺頁次數為0\n");
printf("缺頁率為0\n");
}
else
{
int noPage=0;
int i,j,m;
int bc1[100];
for(i=0;i<blockCount;i++)
{
bc1[i]=0;
}
for(i=0;i<pageCount;i++)
{
// printf("引用頁：%d\n",pc[i]);
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i];
for(int p=0;p<=i;p++)
{
bc1[p]++;
}
}
else
{
for(j=0;j<blockCount;j++)
{
bc1[j]++;
}
int k=FoundMaxNum(bc1,blockCount);
bc[k]=pc[i];
bc1[k]=1;
}
noPage++;
//printf("物理快情況：\n");
//Print(bc,blockCount);
}
else if(Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
for(j=0;j<=i;j++)
{
bc1[j]++;
}
for(m=0;m<=i;m++)
{
if(bc[m]==pc[i])
{
break;
}
}
bc1[m]=1;
bc[m]=pc[i];
}
else
{
for(j=0;j<blockCount;j++)
{
bc1[j]++;
}
for(m=0;m<blockCount;m++)
{
if(bc[m]==pc[i])
{
break;
}
}
bc1[m]=1;
bc[m]=pc[i];
}
}
//printf("\n");
}
printf("LRU缺頁次數為:%d\n",noPage);
printf("LRU缺頁率為:%.2f%%\n",(float)noPage/pageCount*100);
}
}
void Optiomal(int pc[],int bc[],int pageCount,int blockCount)
{
printf("2：最佳置換演算法\n");
if(pageCount<=blockCount)
{
printf("缺頁次數為0\n");
printf("缺頁率為0\n");
}
else
{
int noPage=0;
int i,j,k;
for(i=0;i<pageCount;i++)
{
// printf("引用頁：%d\n",pc[i]);
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i];
}
else
{
int max=0;
int blockIndex;;
for(j=0;j<blockCount;j++)
{
for(k=i;k<pageCount;k++)
{
if(bc[j]==pc[k])
{
break;
}
}
if(k>=max)
{
max=k;
blockIndex=j;
}
}
bc[blockIndex]=pc[i];
}
noPage++;
//printf("物理快情況：\n");
//Print(bc,blockCount);
}
//printf("\n");
}
printf("OPT缺頁次數為:%d\n",noPage);
printf("OPT缺頁率為:%.2f%%\n",(float)noPage/pageCount*100);
}
}
int main()
{
int pageCount,blockCount,i,pc[100];
printf("輸入頁面數\n");
scanf("%d",&pageCount);
printf("輸入頁面走向\n");
for(i=0;i<pageCount;i++)
{
scanf("%d",&pc[i]);
}
blockCount=3;//物理塊數
int bc1[100];
printf("\n");
FIFO(pc,bc1,pageCount,blockCount);
int bc2[100];
printf("\n");
LRU(pc,bc2,pageCount,blockCount);
int bc3[100];
printf("\n");
Optiomal(pc,bc3,pageCount,blockCount);
return 0;
}
B. 操作系統課程設計，用C#實現內存頁面的置換。實現演算法間比較
頁面置換演算法
一．題目要求：
通過實現頁面置換演算法的FIFO和LRU兩種演算法，理解進程運行時系統是怎樣選擇換出頁面的，對於兩種不同的演算法各自的優缺點是哪些。
要求設計主界面以靈活選擇某演算法，且以下演算法都要實現 1) 最佳置換演算法(OPT)：將以後永不使用的或許是在最長(未來)時間內不再被訪問的頁面換出。
2) 先進先出演算法(FIFO)：淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰。
3) 最近最久未使用演算法(LRU)：淘汰最近最久未被使用的頁面。 4) 最不經常使用演算法(LFU) 二．實驗目的：
1、用C語言編寫OPT、FIFO、LRU，LFU四種置換演算法。 2、熟悉內存分頁管理策略。 3、了解頁面置換的演算法。 4、掌握一般常用的調度演算法。 5、根據方案使演算法得以模擬實現。 6、鍛煉知識的運用能力和實踐能力。 三、設計要求
1、編寫演算法，實現頁面置換演算法FIFO、LRU；
2、針對內存地址引用串，運行頁面置換演算法進行頁面置換； 3、演算法所需的各種參數由輸入產生（手工輸入或者隨機數產生）； 4、輸出內存駐留的頁面集合，頁錯誤次數以及頁錯誤率；
四．相關知識：
1．虛擬存儲器的引入：
局部性原理：程序在執行時在一較短時間內僅限於某個部分；相應的，它所訪問的存儲空間也局限於某個區域，它主要表現在以下兩個方面：時間局限性和空間局限性。
2．虛擬存儲器的定義：
虛擬存儲器是只具有請求調入功能和置換功能，能從邏輯上對內存容量進行擴充的一種存儲器系統。
3．虛擬存儲器的實現方式：
分頁請求系統，它是在分頁系統的基礎上，增加了請求調頁功能、頁面置換功能所形成的頁面形式虛擬存儲系統。
請求分段系統，它是在分段系統的基礎上，增加了請求調段及分段置換功能後，所形成的段式虛擬存儲系統。
4．頁面分配：
平均分配演算法，是將系統中所有可供分配的物理塊，平均分配給各個進程。 按比例分配演算法，根據進程的大小按比例分配物理塊。
考慮優先的分配演算法，把內存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進程；另一部分則根據個進程的優先權，適當的增加其相應份額後，分配給各進程。
5．頁面置換演算法：
常用的頁面置換演算法有OPT、FIFO、LRU、Clock、LFU、PBA等。 五、設計說明
1、採用數組頁面的頁號
2、FIFO演算法，選擇在內存中駐留時間最久的頁面予以淘汰；
分配n個物理塊給進程，運行時先把前n個不同頁面一起裝入內存，然後再從後面逐一比較，輸出頁面及頁錯誤數和頁錯誤率。
3、LRU演算法，根據頁面調入內存後的使用情況進行決策；
同樣分配n個物理塊給進程，前n個不同頁面一起裝入內存，後面步驟與前一演算法類似。
選擇置換演算法，先輸入所有頁面號，為系統分配物理塊，依次進行置換： 六．設計思想：
OPT基本思想：
是用一維數組page[pSIZE]存儲頁面號序列，memery[mSIZE]是存儲裝入物理塊中的頁面。數組next[mSIZE]記錄物理塊中對應頁面的最後訪問時間。每當發生缺頁時，就從物理塊中找出最後訪問時間最大的頁面，調出該頁，換入所缺的頁面。
FIFO基本思想：
是用隊列存儲內存中的頁面，隊列的特點是先進先出，與該演算法是一致的，所以每當發生缺頁時，就從隊頭刪除一頁，而從隊尾加入缺頁。或者藉助輔助數組time[mSIZE]記錄物理塊中對應頁面的進入時間，每次需要置換時換出進入時間最小的頁面。
LRU基本思想：
是用一維數組page[pSIZE]存儲頁面號序列，memery[mSIZE]是存儲裝入物理塊中的頁面。數組flag[10]標記頁面的訪問時間。每當使用頁面時，刷新訪問時間。發生缺頁時，就從物理塊中頁面標記最小的一頁，調出該頁，換入所缺的頁面。 七．流程圖：
如下頁所示
六．運行結果： 1. 按任意鍵進行初始化：
2. 載入數據：
3. 進入置換演算法選擇界面：
4.運算中延遲操作：
5.三種演算法演示結果：
C. 操作系統課程設計
設計題目
1設計題目：CPU調度(CPU調度演算法的模擬實現)
具體內容：編寫演算法，實現CPU調度演算法FCFS、非搶佔SJF、可搶占優先權調度、RR
針對模擬進程，利用CPU調度演算法進行調度
進行演算法評價，計算平均周轉時間和平均等待時間
要求：調度所需的進程參數由輸入產生
手工輸入
隨機數產生
輸出調度結果
輸出雞撣慣趕甙非軌石憨將演算法評價指標
2設計題目：虛擬內存 (頁面置換演算法的模擬實現)
具體內容：編寫演算法，實現頁面置換演算法FIFO、LRU
針對內存地址引用串，運行頁面置換演算法進行頁面置換
要求：演算法所需的引用串參數由輸入產生：可由手工輸入也可基於隨機數產生
輸出內存駐留的頁面集合
1．進程調度演算法模塊
[問題描述]
1、進程調度演算法：採用動態最高優先數優先的調度演算法（即把處理機分配給優先數最高的進程）。
2、每個進程有一個進程式控制制塊（ PCB）表示。進程式控制制塊可以包含如下信息：
進程名---進程標示數 ID
優先數 PRIORITY 優先數越大優先權越高
到達時間---進程的到達時間為進程輸入的時間。、
進程還需要運行時間ALLTIME，進程運行完畢ALLTIME=0，
已用CPU時間----CPUTIME、
進程的阻塞時間STARTBLOCK-表示當進程在運行STARTBLOCK個時間片後，進程將進入阻塞狀態
進程的阻塞時間BLOCKTIME--表示當進程阻塞BLOCKTIME個時間片後，進程將進入就緒狀態
進程狀態—STATE
隊列指針NEXT 用來將PCB排成隊列。
3、調度原則：
進程的優先數及需要的運行時間可以事先人為地指定（也可以由隨機數產生）。進程的到達時間為進程輸入的時間。
進程的運行時間以時間片為單位進行計算。
進程在就緒隊列中待一個時間片，優先數加1
每個進程的狀態可以是就緒 R（READY）、運行R（Run）阻塞B(BLOCK)、或完成F（Finish）四種狀態之一。
就緒進程獲得 CPU後都只能運行一個時間片。用已佔用CPU時間加1來表示。
如果運行一個時間片後，進程的已佔用CPU時間已達到所需要的運行時間，則撤消該進程，如果運行一個時間片後進程的已佔用CPU時間還未達所需要的運行時間，也就是進程還需要繼續運行，此時應將進程的優先數減3，然後把它插入就緒隊列等待CPU。
每進行一次調度程序都列印一次運行進程、就緒隊列、以及各個進程的 PCB，以便進行檢查。
重復以上過程，直到所要進程都完成為止。
求課程設計報告和用c語言編寫的源代碼
D. 分頁式存儲管理頁面置換演算法C語言描述，幫忙看一下錯誤
init裡面那個for循環，k沒有初始化就直接用，沒問題嗎？local variable不初始化，貌似不是默認初始化為0的。還有這個邏輯是什麼意思：
if(k<4){
pagelist[k].id=1;
pagelist[k].chid=0;
}
E. 用C++語言編寫FIFO頁面置換演算法代碼
分別使用FIFO、OPT、LRU三種置換演算法來模擬頁面置換的過程。（Linux、Windows下皆可）
輸入：3//頁幀數
70120304230321201701//待處理的頁
輸出：頁面置換過程中各幀的變化過程和出現頁錯誤的次數
[cpp]
#include<iostream>
usingnamespacestd;
intinput[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
classpage
{
public:
intnum;
intmark;
page()
{
num=0;
mark=21;
}
};
voidFIFO()
{
cout<<"------FIFO-----------"<<endl;
interror=0;
pageframe[3];//頁幀
for(inti=0;i<3;i++)//處理前三個引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
frame[((error-1)%3)].num=input[i];//換掉最舊的頁
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
voidOPT()
{
cout<<"------OPT------------"<<endl;
interror=0;
pageframe[3];
for(inti=0;i<3;i++)//處理前三個引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
for(j=0;j<3;j++)
{
frame[j].mark=21;
for(intk=20;k>=i;k--)//向後遍歷，找到最長時間不用的頁
{
if(frame[j].num==input[k])
frame[j].mark=k;
}
}
if(frame[0].mark>frame[1].mark&&frame[0].mark>frame[2].mark)
frame[0].num=input[i];
elseif(frame[1].mark>frame[0].mark&&frame[1].mark>frame[2].mark)
frame[1].num=input[i];
else
frame[2].num=input[i];
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
voidLRU()
{
cout<<"------LRU------------"<<endl;
interror=0;
pageframe[3];
for(inti=0;i<3;i++)//處理前三個引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
for(j=0;j<3;j++)
{
frame[j].mark=0;
for(intk=0;k<=i;k++)//向前遍歷，找到最近最少使用的
{
if(frame[j].num==input[k])
frame[j].mark=k;
}
}
if(frame[0].mark<frame[1].mark&&frame[0].mark<frame[2].mark)
frame[0].num=input[i];
elseif(frame[1].mark<frame[0].mark&&frame[1].mark<frame[2].mark)
frame[1].num=input[i];
else
frame[2].num=input[i];
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
intmain()
{
FIFO();
OPT();
LRU();
}
F. 請求調頁存儲管理方式的模擬,謝謝，急 啊 ！
這可是hen寶貴的啊
#include <iostream.h>
#include<stdlib.h>
#include<conio.h>
#include<stdio.h>
#define Bsize 4
typedef struct BLOCK//聲明一種新類型——物理塊類型
{
int pagenum;//頁號
int accessed;//訪問欄位，其值表示多久未被訪問
}BLOCK;
int pc;//程序計數器，用來記錄指令的序號
int n;//缺頁計數器，用來記錄缺頁的次數
static int temp[320];//用來存儲320條隨機數
BLOCK block[Bsize]; //定義一大小為4的物理塊數組
//*************************************************************
void init( ); //程序初始化函數
int findExist(int curpage);//查找物理塊中是否有該頁面
int findSpace( );//查找是否有空閑物理塊
int findReplace( );//查找應予置換的頁面
void display ( );//顯示
void suijishu( );//產生320條隨機數,顯示並存儲到temp[320]
void pagestring( );//顯示調用的頁面隊列
void OPT( );//OPT演算法
void LRU( );// LRU演算法
void FIFO( );//FIFO演算法
//*************************************************************
void init( )
{
for(int i=0;i<Bsize;i++)
{
block[i].pagenum=-1;
block[i].accessed=0;
pc=n=0;
}
}
//-------------------------------------------------------------
int findExist(int curpage)
{
for(int i=0; i<Bsize; i++)
{
if(block[i].pagenum == curpage )
return i;//檢測到內存中有該頁面，返回block中的位置
}
return -1;
}
//-------------------------------------------------------------
int findSpace( )
{
for(int i=0; i<Bsize; i++)
{
if(block[i].pagenum == -1)
return i;//找到空閑的block，返回block中的位置
}
return -1;
}
//-------------------------------------------------------------
int findReplace( )
{
int pos = 0;
for(int i=0; i<Bsize; i++)
{
if(block[i].accessed >block[pos].accessed)
pos = i;//找到應予置換頁面，返回BLOCK中位置
}
return pos;
}
//-------------------------------------------------------------
void display( )
{
for(int i=0; i<Bsize; i++)
{
if(block[i].pagenum != -1)
{ printf(" %02d",block[i].pagenum);}
}
cout<<endl;
}
//-------------------------------------------------------------
void suijishu( )
{ int flag=0;
cin>>pc;
cout<<"******按照要求產生的320個隨機數：*******"<<endl;
for(int i=0;i<320;i++)
{
temp[i]=pc;
if(flag%2==0) pc=++pc%320;
if(flag==1) pc=rand( )% (pc-1);
if(flag==3) pc=pc+1+(rand( )%(320-(pc+1)));
flag=++flag%4;
printf(" %03d",temp[i]);
if((i+1)%10==0) cout<<endl;
}
}
//-------------------------------------------------------------
void pagestring( )
{
for(int i=0;i<320;i++)
{
printf(" %02d",temp[i]/10);
if((i+1)%10==0) cout<<endl;
}
}
//-------------------------------------------------------------
void OPT( )
{
int exist,space,position ;
int curpage;
for(int i=0;i<320;i++)
{
if(i%100==0) getch( );
pc=temp[i];
curpage=pc/10;
exist = findExist(curpage);
if(exist==-1)
{
space = findSpace ( );
if(space != -1)
{
block[space].pagenum = curpage;
display( );
n=n+1;
}
else
{
for(int k=0;k<Bsize;k++)
{
for(int j=i;j<320;j++)
{
if(block[k].pagenum!= temp[j]/10)
{
block[k].accessed = 1000;
}//將來不會用，設置為一個很大數
else
{
block[k].accessed = j;
break;
}
}
}
position = findReplace( );
block[position].pagenum = curpage;
display( );
n++;
}
}
}
cout<<"缺頁次數:"<<n<<endl;
cout<<"缺頁率:"<<(n/320.0)*100<<"%"<<endl;
}
//-------------------------------------------------------------
void LRU( )
{
int exist,space,position ;
int curpage;
for(int i=0;i<320;i++)
{
if(i%100==0) getch( );
pc=temp[i];
curpage=pc/10;
exist = findExist(curpage);
if(exist==-1)
{
space = findSpace( );
if(space != -1)
{
block[space].pagenum = curpage;
display( );
n=n+1;
}
else
{
position = findReplace( );
block[position].pagenum = curpage;
display( );
n++;
}
}
else block[exist].accessed = -1;//恢復存在的並剛訪問過的BLOCK中頁面accessed為-1
for(int j=0; j<4; j++)
{block[j].accessed++;}
}
cout<<"缺頁次數:"<<n<<endl;
cout<<"缺頁率:"<<(n/320.0)*100<<"%"<<endl;
}
//-------------------------------------------------------------
void FIFO( )
{
int exist,space,position ;
int curpage;
for(int i=0;i<320;i++)
{
if(i%100==0) getch( );
pc=temp[i];
curpage=pc/10;
exist = findExist(curpage);
if(exist==-1)
{
space = findSpace( );
if(space != -1)
{
block[space].pagenum = curpage;
display( );
n=n+1;
}
else
{
position = findReplace( );
block[position].pagenum = curpage;
display( );
n++;
block[position].accessed--;
}
}
for(int j=0; j<Bsize; j++)
block[j].accessed++;
}
cout<<"缺頁次數:"<<n<<endl;
cout<<"缺頁率:"<<(n/320.0)*100<<"%"<<endl;
}
//*************************************************************
void main( )
{
int select;
cout<<"請輸入第一條指令號(0~320)：";
suijishu( );
cout<<"*****對應的調用頁面隊列*******"<<endl;
pagestring( );
do
{
cout<<"****************************************"<<endl;
cout<<"------1:OPT 2:LRU 3:FIFO 4:退出-----"<<endl;
cout<<"****************************************"<<endl;
cout<<" 請選擇一種頁面置換演算法:";
cin>>select;
cout<<"****************************************"<<endl;
init( );
switch(select)
{
case 1:cout<<"最佳置換演算法OPT:"<<endl;
cout<<"*****************"<<endl;
OPT( );
break;
case 2:cout<<"最近最久未使用置換演算法LRU:"<<endl;
cout<<"**************************"<<endl;
LRU( );
break;
case 3:cout<<"先進先出置換演算法FIFO:"<<endl;
cout<<"*********************"<<endl;
FIFO( );
break;
default: ;
}
}while(select!=4);
}
你試試可以不，應該沒問題的
要注意這是用C++編寫的，你改一下就可以用了