A. 求頁式虛擬存儲技術的原理。
虛擬存儲器是根據程序的邏輯地址轉換來的，也稱線性地址空間。一般每個進程，甚至每個段都有一個，以32位為例，則每個最大可達4G。 而主存目前一般為百M。因此程序中所指的存儲單元並不能都放到主存中，也就是並不是每個程序所用的存儲單元，都有具體的物理的存儲器單元與之對應。 但由於程序的兩個局部性原理，在一個時刻，程序只在一個比較小的范圍內運行。所以我們把程序可能用到的整個存儲空間分成一個個相同大小的頁(按頁管理硬體上容易實現)，只把其中的一些頁放在主存中，而其它的頁則等需要時再建，或放在輔存(磁碟)中。同時建立一個頁表，對應於每一頁，如果該頁在主存中，則頁表記錄它在主存中的地址；如果不在主存中，則在頁表上作不在主存的標記。 這樣，當程序需要調用某個存儲單元的內容時，先根據它的線性地址，算出其所在的頁。查頁表，看是不是在主存中？如果在，則直接存取。如果查到頁表上是不在的標記，那就是一個page fault。要把主存中的某一頁(LRU策略)換到磁碟上，把要訪問的那個單元所在的頁調入主存，再進行存取。 就象一個預計有一萬學生的學校，理論上每個學生都應有一個位子上課(一萬個虛擬位子)，而學校只有一千個(物理)位子。但實際上，學校也不會一萬個人同時上課，只要讓上課的同學有位子(在主存中)，而其它同學只要留下聯系方法能找到就好。為了降低管理的復雜性，我們採用按學號分班(頁)管理。每個班要麼一起上課(主存)，要麼一起呆在寢室(磁碟)。而在學校保留一個動態表(頁表)表明每個班在哪兒(物理地址)上課，或者沒上課(不在主存)。現在假設我們想按學號找一個同學，而且是女同學，只能在教室說話，呵呵。那麼： 先算出來是哪個班的，查動態表，看該班是否在教室。在，直接按位置找到(hit)；不在(page fault)，要先找個不上課的班趕回寢室，把要找女生所在的班調到教室，再按位置找那個同學。 動態表(頁表)的大小＝表項數＊每個表項所需的位數。 表項數＝虛擬班數＝虛擬人數(虛擬地址空間)/每班人數(每頁大小) 每個表項的位數＝Log(教室數)+適當控制位數
麻煩採納，謝謝!
B. 模擬頁式虛擬存儲管理中硬體地址變換和缺頁中斷，並用LRU演算法處理缺頁中斷，用C語言做
這個問題太專業，人我不知道。
C. 操作系統頁式存儲管理的問題
邏輯頁面表示這是一個虛擬的儲存空間，一個邏輯頁面對應一個物理內存的頁框，這個頁框才是真正的物理存儲所在。
D. Linux實驗,頁式虛存的模擬實現
有沒有搞錯，這樣的東西做好了可能賣錢了都，一點分都不給啊！
E. 操作系統
實驗七 存儲管理---------常用頁面置換演算法模擬實驗
實驗目的
通過模擬實現請求頁式存儲管理的幾種基本頁面置換演算法，了解虛擬存儲技術的特點，掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換演算法的基本思想和實現過程，並比較它們的效率。
實驗內容
設計一個虛擬存儲區和內存工作區，並使用下述演算法計算訪問命中率。
1、最佳淘汰演算法（OPT）
2、先進先出的演算法（FIFO）
3、最近最久未使用演算法（LRU）
4、最不經常使用演算法（LFU）
5、最近未使用演算法（NUR）
命中率＝1－頁面失效次數／頁地址流長度
實驗准備
本實驗的程序設計基本上按照實驗內容進行。即首先用srand( )和rand( )函數定義和產生指令序列，然後將指令序列變換成相應的頁地址流，並針對不同的演算法計算出相應的命中率。
（1）通過隨機數產生一個指令序列，共320條指令。指令的地址按下述原則生成：
A：50%的指令是順序執行的
B：25%的指令是均勻分布在前地址部分
C：25%的指令是均勻分布在後地址部分
具體的實施方法是：
A：在[0，319]的指令地址之間隨機選取一起點m
B：順序執行一條指令，即執行地址為m+1的指令
C：在前地址[0,m+1]中隨機選取一條指令並執行，該指令的地址為m』
D：順序執行一條指令，其地址為m』+1
E：在後地址[m』+2，319]中隨機選取一條指令並執行
F：重復步驟A-E，直到320次指令
（2）將指令序列變換為頁地址流
設：頁面大小為1K；
用戶內存容量4頁到32頁；
用戶虛存容量為32K。
在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為：
第 0 條-第 9 條指令為第0頁（對應虛存地址為[0，9]）
第10條-第19條指令為第1頁（對應虛存地址為[10，19]）
………………………………
第310條-第319條指令為第31頁（對應虛存地址為[310，319]）
按以上方式，用戶指令可組成32頁。
實驗指導
一、虛擬存儲系統
UNIX中，為了提高內存利用率，提供了內外存進程對換機制；內存空間的分配和回收均以頁為單位進行；一個進程只需將其一部分（段或頁）調入內存便可運行；還支持請求調頁的存儲管理方式。
當進程在運行中需要訪問某部分程序和數據時，發現其所在頁面不在內存，就立即提出請求（向CPU發出缺中斷），由系統將其所需頁面調入內存。這種頁面調入方式叫請求調頁。
為實現請求調頁，核心配置了四種數據結構：頁表、頁框號、訪問位、修改位、有效位、保護位等。
二、頁面置換演算法
當 CPU接收到缺頁中斷信號，中斷處理程序先保存現場，分析中斷原因，轉入缺頁中斷處理程序。該程序通過查找頁表，得到該頁所在外存的物理塊號。如果此時內存未滿，能容納新頁，則啟動磁碟I/O將所缺之頁調入內存，然後修改頁表。如果內存已滿，則須按某種置換演算法從內存中選出一頁准備換出，是否重新寫盤由頁表的修改位決定，然後將缺頁調入，修改頁表。利用修改後的頁表，去形成所要訪問數據的物理地址，再去訪問內存數據。整個頁面的調入過程對用戶是透明的。
常用的頁面置換演算法有
1、最佳置換演算法（Optimal）
2、先進先出法（Fisrt In First Out）
3、最近最久未使用（Least Recently Used）
4、最不經常使用法（Least Frequently Used）
5、最近未使用法（No Used Recently）
三、參考程序：
#define TRUE 1
#define FALSE 0
#define INVALID -1
#define NULL 0
#define total_instruction 320 /*指令流長*/
#define total_vp 32 /*虛頁長*/
#define clear_period 50 /*清0周期*/
typedef struct /*頁面結構*/
{
int pn,pfn,counter,time;
}pl_type;
pl_type pl[total_vp]; /*頁面結構數組*/
struct pfc_struct{ /*頁面控制結構*/
int pn,pfn;
struct pfc_struct *next;
};
typedef struct pfc_struct pfc_type;
pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
int diseffect, a[total_instruction];
int page[total_instruction], offset[total_instruction];
int initialize(int);
int FIFO(int);
int LRU(int);
int LFU(int);
int NUR(int);
int OPT(int);
int main( )
{
int s,i,j;
srand(10*getpid()); /*由於每次運行時進程號不同，故可用來作為初始化隨機數隊列的「種子」*/
s=(float)319*rand( )/32767/32767/2+1; //
for(i=0;i<total_instruction;i+=4) /*產生指令隊列*/
{
if(s<0||s>319)
{
printf("When i==%d,Error,s==%d\n",i,s);
exit(0);
}
a[i]=s; /*任選一指令訪問點m*/
a[i+1]=a[i]+1; /*順序執行一條指令*/
a[i+2]=(float)a[i]*rand( )/32767/32767/2; /*執行前地址指令m' */
a[i+3]=a[i+2]+1; /*順序執行一條指令*/
s=(float)(318-a[i+2])*rand( )/32767/32767/2+a[i+2]+2;
if((a[i+2]>318)||(s>319))
printf("a[%d+2],a number which is :%d and s==%d\n",i,a[i+2],s);
}
for (i=0;i<total_instruction;i++) /*將指令序列變換成頁地址流*/
{
page[i]=a[i]/10;
offset[i]=a[i]%10;
}
for(i=4;i<=32;i++) /*用戶內存工作區從4個頁面到32個頁面*/
{
printf("---%2d page frames---\n",i);
FIFO(i);
LRU(i);
LFU(i);
NUR(i);
OPT(i);
}
return 0;
}
int initialize(total_pf) /*初始化相關數據結構*/
int total_pf; /*用戶進程的內存頁面數*/
{int i;
diseffect=0;
for(i=0;i<total_vp;i++)
{
pl[i].pn=i;
pl[i].pfn=INVALID; /*置頁面控制結構中的頁號，頁面為空*/
pl[i].counter=0;
pl[i].time=-1; /*頁面控制結構中的訪問次數為0，時間為-1*/
}
for(i=0;i<total_pf-1;i++)
{
pfc[i].next=&pfc[i+1];
pfc[i].pfn=i;
} /*建立pfc[i-1]和pfc[i]之間的鏈接*/
pfc[total_pf-1].next=NULL;
pfc[total_pf-1].pfn=total_pf-1;
freepf_head=&pfc[0]; /*空頁面隊列的頭指針為pfc[0]*/
return 0;
}
int FIFO(total_pf) /*先進先出演算法*/
int total_pf; /*用戶進程的內存頁面數*/
{
int i,j;
pfc_type *p;
initialize(total_pf); /*初始化相關頁面控制用數據結構*/
busypf_head=busypf_tail=NULL; /*忙頁面隊列頭，隊列尾鏈接*/
for(i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID) /*頁面失效*/
{
diseffect+=1; /*失效次數*/
if(freepf_head==NULL) /*無空閑頁面*/
{
p=busypf_head->next;
pl[busypf_head->pn].pfn=INVALID;
freepf_head=busypf_head; /*釋放忙頁面隊列的第一個頁面*/
freepf_head->next=NULL;
busypf_head=p;
}
p=freepf_head->next; /*按FIFO方式調新頁面入內存頁面*/
freepf_head->next=NULL;
freepf_head->pn=page[i];
pl[page[i]].pfn=freepf_head->pfn;
if(busypf_tail==NULL)
busypf_head=busypf_tail=freepf_head;
else
{
busypf_tail->next=freepf_head; /*free頁面減少一個*/
busypf_tail=freepf_head;
}
freepf_head=p;
}
}
printf("FIFO:%6.4f\n",1-(float)diseffect/320);
return 0;
}
int LRU (total_pf) /*最近最久未使用演算法*/
int total_pf;
{
int min,minj,i,j,present_time;
initialize(total_pf);
present_time=0;
for(i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID) /*頁面失效*/
{
diseffect++;
if(freepf_head==NULL) /*無空閑頁面*/
{
min=32767;
for(j=0;j<total_vp;j++) /*找出time的最小值*/
if(min>pl[j].time&&pl[j].pfn!=INVALID)
{
min=pl[j].time;
minj=j;
}
freepf_head=&pfc[pl[minj].pfn]; //騰出一個單元
pl[minj].pfn=INVALID;
pl[minj].time=-1;
freepf_head->next=NULL;
}
pl[page[i]].pfn=freepf_head->pfn; //有空閑頁面,改為有效
pl[page[i]].time=present_time;
freepf_head=freepf_head->next; //減少一個free 頁面
}
else
pl[page[i]].time=present_time; //命中則增加該單元的訪問次數
present_time++;
}
printf("LRU:%6.4f\n",1-(float)diseffect/320);
return 0;
}
int NUR(total_pf) /*最近未使用演算法*/
int total_pf;
{ int i,j,dp,cont_flag,old_dp;
pfc_type *t;
initialize(total_pf);
dp=0;
for(i=0;i<total_instruction;i++)
{ if (pl[page[i]].pfn==INVALID) /*頁面失效*/
{diseffect++;
if(freepf_head==NULL) /*無空閑頁面*/
{ cont_flag=TRUE;
old_dp=dp;
while(cont_flag)
if(pl[dp].counter==0&&pl[dp].pfn!=INVALID)
cont_flag=FALSE;
else
{
dp++;
if(dp==total_vp)
dp=0;
if(dp==old_dp)
for(j=0;j<total_vp;j++)
pl[j].counter=0;
}
freepf_head=&pfc[pl[dp].pfn];
pl[dp].pfn=INVALID;
freepf_head->next=NULL;
}
pl[page[i]].pfn=freepf_head->pfn;
freepf_head=freepf_head->next;
}
else
pl[page[i]].counter=1;
if(i%clear_period==0)
for(j=0;j<total_vp;j++)
pl[j].counter=0;
}
printf("NUR:%6.4f\n",1-(float)diseffect/320);
return 0;
}
int OPT(total_pf) /*最佳置換演算法*/
int total_pf;
{int i,j, max,maxpage,d,dist[total_vp];
pfc_type *t;
initialize(total_pf);
for(i=0;i<total_instruction;i++)
{ //printf("In OPT for 1,i=%d\n",i); //i=86;i=176;206;250;220,221;192,193,194;258;274,275,276,277,278;
if(pl[page[i]].pfn==INVALID) /*頁面失效*/
{
diseffect++;
if(freepf_head==NULL) /*無空閑頁面*/
{for(j=0;j<total_vp;j++)
if(pl[j].pfn!=INVALID) dist[j]=32767; /* 最大"距離" */
else dist[j]=0;
d=1;
for(j=i+1;j<total_instruction;j++)
{
if(pl[page[j]].pfn!=INVALID)
dist[page[j]]=d;
d++;
}
max=-1;
for(j=0;j<total_vp;j++)
if(max<dist[j])
{
max=dist[j];
maxpage=j;
}
freepf_head=&pfc[pl[maxpage].pfn];
freepf_head->next=NULL;
pl[maxpage].pfn=INVALID;
}
pl[page[i]].pfn=freepf_head->pfn;
freepf_head=freepf_head->next;
}
}
printf("OPT:%6.4f\n",1-(float)diseffect/320);
return 0;
}
int LFU(total_pf) /*最不經常使用置換法*/
int total_pf;
{
int i,j,min,minpage;
pfc_type *t;
initialize(total_pf);
for(i=0;i<total_instruction;i++)
{ if(pl[page[i]].pfn==INVALID) /*頁面失效*/
{ diseffect++;
if(freepf_head==NULL) /*無空閑頁面*/
{ min=32767;
for(j=0;j<total_vp;j++)
{if(min>pl[j].counter&&pl[j].pfn!=INVALID)
{
min=pl[j].counter;
minpage=j;
}
pl[j].counter=0;
}
freepf_head=&pfc[pl[minpage].pfn];
pl[minpage].pfn=INVALID;
freepf_head->next=NULL;
}
pl[page[i]].pfn=freepf_head->pfn; //有空閑頁面,改為有效
pl[page[i]].counter++;
freepf_head=freepf_head->next; //減少一個free 頁面
}
else
pl[page[i]].counter++;
}
printf("LFU:%6.4f\n",1-(float)diseffect/320);
return 0;
}
四、運行結果
4 page frams
FIFO: 0.7312
LRU: 0.7094
LFU: 0.5531
NUR: 0.7688
OPT: 0.9750
5 page frams
…………
五、分析
1、從幾種演算法的命中率看，OPT最高，其次為NUR相對較高，而FIFO與LRU相差無幾，最低的是LFU。但每個頁面執行結果會有所不同。
2、OPT演算法在執行過程中可能會發生錯誤
五、思考
1、為什麼OPT在執行時會有錯誤產生？
F. 請求頁式管理是一種常用的虛擬存儲管理技術。
14、虛擬存儲器：是由主存、輔寸、存儲管理單元及操作系統中存儲管理軟體組成的存儲系統。 分類： 頁式虛擬存儲器(以頁為信息傳送單 優點：頁表硬體少，