記憶體中的程序
•記憶體一部分供作業系統使用（駐留監控程式、核心），一部分供目前活躍的程序使用，用于存放程序需要的資料和程式等。 •記憶體管理最基本的操作是由處理器把程式裝入記憶體中執行。
•程序對應的記憶體空間包含5種不同的資料區：
代碼段（Text）：代碼段是用來存放可執行檔案的操作指令，也就是說是它是可執行程式在記憶體中的鏡像。
資料段（Data）：資料段存放可執行檔案中已初始化全局變量，包括程式靜态(static)配置設定變量和全局變量(global)。
BSS段：BSS段包含了程式中未初始化的全局變量和靜态變量，在記憶體中 bss段全部置零。
堆（Heap）：堆是用于存放程序運作中被動态配置設定(malloc)的記憶體段。
棧（Stack）：棧是使用者存放程式臨時建立的局部變量。除此以外，在函數被調用時，其參數也會被壓入發起調用的程序棧中，并且待到調用結束後，函數的傳回值也會被存放回棧中。
在linux環境下編寫程式，模拟一個作業的執行過程。
•使用者輸入系統配置設定給該作業的實體塊N，和該作業要通路的邏輯頁号序列長度L。 •該作業要通路的邏輯頁号序列可以使用者輸入，也可以采用某種政策生成，如随機。 •采用下面不同的頁面置換算法，并給出不同算法下的頁面置換情況及其對應的缺頁率。 •FIFO--先進先出，置換駐留在記憶體中時間最長的頁。 •LRU--最近最少使用，置換記憶體中上次使用據目前最遠的頁。 •OPT--最佳置換，未來通路據目前時間最長的頁。 •CLOCK--時鐘算法，頁框關聯使用位。
為了好看（我為啥每次都在這種意義不明的事情上那麼麻煩……）做了類指令行的操作界面，明明就是個控制台至于麼…… 每個函數和使用者友好表達都封裝成函數，自認為寫起來還是比較清晰明朗的（都劃分這麼細了了好不好） 純原創，請勿随意轉載使用，如需使用請告知或署名okcd00，謝謝。
Code:
#include <cmath>
#include <time.h>
#include <cctype>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <windows.h>
#include <iostream>
#include <algorithm>
using namespace std;
int b[16]; //block
int mem[256]; //memory
string choice; //choice
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
int n,l;
bool cmp(const int a, const int b)
{
return a > b;
}
void sta() //start
{
cout<<"<Project4> = 20125209 IOT01 Chendian_陳點"<<endl;
cout<<"Please input the number of Physic Blocks (Less than 15):"; cin>>n;
cout<<"Please input the Length of Sequence Length (Less than 255):";cin>>l;
}
void cus() //custom
{
cout<<"==Custom Setting=="<<endl;
cout<<"Please Input "<<l<<" digits :(split with blank)"<<endl;
for(int i=0;i<l;i++)
{
cin>>mem[i];
}
cout<<"\n Custom_Set Finished"<<endl;
}
void ran() //random
{
srand(time(NULL));
cout<<"==Random Setting=="<<endl;
cout<<"Now Calculating";
cout<<endl;
for(int i=0;i<l;i++)
{
mem[i]=rand()%8+1;
cout<<".";
}
cout<<"\n Random_Set Finished"<<endl;
}
void inp() //input
{
cout<<"Do you want CUSTOM or RANDOM?(c/r):"<<endl;
memset(mem,0,sizeof mem);
while(1)
{
cin>>choice;
if(tolower(choice[0])=='c') {cus();break;}
if(tolower(choice[0])=='r') {ran();break;}
//7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
cout<<"Invalid Input , Please Try again:";
}
}
void dis() //display
{
cout<<endl <<"@ FIFO -- 先進先出，置換駐留在記憶體中時間最長的頁"<<endl
<<"@ LRU -- 最近最少使用，置換記憶體中上次使用據目前最遠的頁"<<endl
<<"@ OPT -- 最佳置換，未來通路據目前時間最長的頁"<<endl
<<"@ CLOCK-- 時鐘算法，頁框關聯使用位"<<endl
<<"@ Exit -- 退出 "<<endl
<<"@ Another Sequence -- 更換序列 "<<endl
<<"Please Select Replacing Algorithm(輸入首字母即可):"<<endl;
}
void fif() //fifo
{
int pos=0;
int cnt=0;
memset(b,-1,sizeof b);
for(int i=0;i<l;i++)
{
int now=mem[i],f=0;
for(int j=0;j<n;j++) if(b[j]==now) { f=1;break;}
if(f)
{
for(int j=0;j<n;j++) if(b[j]==-1)printf("# ");else printf("%d ",b[j]);
printf("[命中]\t New is %d\n",now);
}
else
{
b[pos++]=now;
pos=pos%n;
cnt++;
for(int j=0;j<n;j++) if(b[j]==-1)printf("# ");else printf("%d ",b[j]);
printf("[缺頁]\t New is %d\n",now);
}
}
cout<<"缺頁數:"<<cnt<<endl;
cout<<"缺頁率:"<<(double)cnt/(double)l *100.0 <<"%"<<endl;
}
void lru() //lru
{
int maxdis=-1;
int chg=0,cnt=0;
int rec[10]={0}; //record
int dis[10]={0}; //distance
memset(b,-1,sizeof b);
for(int i=0;i<l;i++)
{
maxdis=-1;
int now=mem[i],f=0;
for(int j=0;j<n;j++)
{
if(b[j]==now) {f=1;break;}
if(b[j]==-1) {chg=j;break;}
dis[b[j]]=i-rec[b[j]];
//cout<<"dis["<<j<<"]:"<<dis[b[j]]<<endl;
if(dis[b[j]]>maxdis) maxdis=dis[b[j]],chg=j;
}
if(f)
{
rec[now]=i;
for(int j=0;j<n;j++) if(b[j]==-1)printf("# ");else printf("%d ",b[j]);
printf("[命中]\t New is %d\n",now);
}
else
{
b[chg]=now, cnt++;
rec[now]=i;
for(int j=0;j<n;j++) if(b[j]==-1)printf("# ");else printf("%d ",b[j]);
printf("[缺頁]\t New is %d\n",now);
}
}
cout<<"缺頁數:"<<cnt<<endl;
cout<<"缺頁率:"<<(double)cnt/(double)l *100.0 <<"%"<<endl;
}
void opt() //opt
{
int maxdis=-1;
int cnt=0;
int dis[10]={0}; //distance
memset(b,-1,sizeof b);
for(int i=0;i<l;i++)
{
int pos=0;
int chg=0;
maxdis=-1;
int now=mem[i],f=0;
for(int j=0;j<n;j++)
{
if(b[j]==now) {f=1;break;}
if(b[j]==-1) {chg=j;break;}
dis[b[j]]=0;
for(int k=i+1;k<l;k++)
{
if(mem[k]==b[j])
{
dis[b[j]]=k-i;
break;
}
}
//cout<<"dis["<<j<<"]:"<<dis[b[j]]<<endl;
if(dis[b[j]]>maxdis) maxdis=dis[b[j]],chg=j;
}
if(f)
{
for(int j=0;j<n;j++) if(b[j]==-1)printf("# ");else printf("%d ",b[j]);
printf("[命中]\t New is %d\n",now);
}
else
{
b[chg]=now, cnt++;
for(int j=0;j<n;j++) if(b[j]==-1)printf("# ");else printf("%d ",b[j]);
printf("[缺頁]\t New is %d\n",now);
}
}
cout<<"缺頁數:"<<cnt<<endl;
cout<<"缺頁率:"<<(double)cnt/(double)l *100.0 <<"%"<<endl;
}
void clo() //clock
{
int cnt=0;
int pos=0;
int clk[10]={0}; //clock
int dis[10]={0}; //distance
memset(b,-1,sizeof b);
for(int i=0;i<l;i++)
{
int chg=0;
int now=mem[i],f=0;
while(1)
{
if(b[pos]==now)
{
f=1;
clk[pos]=1;
break;
}
if(b[pos]==-1 || clk[pos]==0)
{
f=0;
chg=pos;
clk[pos]=1;
break;
}
clk[pos]=0;
pos++;
pos=pos%n;
}
if(f==1)
{
for(int j=0;j<n;j++) if(b[j]==-1)printf("# ");else printf("%d ",b[j]);
printf("[命中]\t New is %d\n",now);
}
else if(f==0)
{
b[chg]=now, cnt++;
for(int j=0;j<n;j++) if(b[j]==-1)printf("# ");else printf("%d ",b[j]);
printf("[缺頁]\t New is %d\n",now);
}
}
cout<<"缺頁數:"<<cnt<<endl;
cout<<"缺頁率:"<<(double)cnt/(double)l *100.0 <<"%"<<endl;
}
int main()
{
sta();
inp();
cout<<"==Sequence Setting Finished=="<<endl;
cout<<"Your Sequence is:"<<endl;
for(int i=0;i<l;i++) cout<<mem[i]<<"\t";
while(1)
{
dis();
cin>>choice;
memset(b,0,sizeof b);
if(tolower(choice[0])=='f') fif();
else if(tolower(choice[0])=='l') lru();
else if(tolower(choice[0])=='o') opt();
else if(tolower(choice[0])=='c') clo();
else if(tolower(choice[0])=='a') inp();
else if(tolower(choice[0])=='e') break;
else cout<<"Invalid Input , Please Try again:";
}
cout<<"Thanks for Using"<<endl
<<"\t__Author IOT Chendian 20125209"<<endl;
return 0;
}
實際運作代碼測試
粗略的評析結果
FIFO算法較易實作，對具有線性順序特征的程式比較适用，而對具有其他特征的程式則效率不高，此算法還可能出現抖動現象，當序列為周期為N的重複子序列時效率最低。
LRU算法基于程式的局部性原理，是以應該适用大多數程式，此算法實作需要維護淘汰隊列。
OPT算法雖然産生的缺頁數最少，然而，卻需要預測程式的頁面引用串，大多數情況下這是無法預知的，不可能對程式的運作過程做出精确的斷言，不過此理論算法可用作衡量各種具體算法的标準。
時鐘算法的話，有點像是改進了的FIFO算法，