一、實(shí)驗(yàn)?zāi)康募盎疽?/h1>
設(shè)計(jì)和實(shí)現(xiàn)最佳置換算法、先進(jìn)先出置換算法、最近最久未使用置換算法、頁面緩沖置換算法，改進(jìn)Clock算法；
通過頁面訪問序列隨機(jī)發(fā)生器實(shí)現(xiàn)對上述算法的測試及性能比較。
二、頁面置換算法相關(guān)知識(shí)
如果發(fā)生了缺頁中斷，就需要從磁盤上將需要的頁面調(diào)入內(nèi)存。如果內(nèi)存沒有多余的空間，就需要在現(xiàn)有的頁面中選擇一個(gè)頁面進(jìn)行替換。使用不同的頁面置換算法，頁面更換的順序也會(huì)各不相同。如果挑選的頁面是之后很快又要被訪問的頁面，那么系統(tǒng)將很開再次產(chǎn)生缺頁中斷，因?yàn)榇疟P訪問速度遠(yuǎn)遠(yuǎn)內(nèi)存訪問速度，缺頁中斷的代價(jià)是非常大的。因此，挑選哪個(gè)頁面進(jìn)行置換不是隨隨便便的事情，而是有要求的。
1.頁面置換的目標(biāo)
頁面置換時(shí)挑選頁面的目標(biāo)主要在于降低隨后發(fā)生缺頁中斷的次數(shù)或概率。
因此，挑選的頁面應(yīng)當(dāng)是隨后相當(dāng)長時(shí)間內(nèi)不會(huì)被訪問的頁面，最好是再也不會(huì)被訪問的頁面。但是，如果可能，最好選擇一個(gè)沒有修改過的頁面，這樣替換時(shí)就無須將被替換頁面的內(nèi)容寫回磁盤，從而進(jìn)一步加快缺頁中斷的響應(yīng)速度。
所以，為了達(dá)到這個(gè)目的，設(shè)計(jì)出了各種各樣的頁面置換算法，下面就來看看這些算法。
三、頁面置換算法
1.最佳置換算法
從主存中移出永遠(yuǎn)不再需要的頁面；如無這樣的頁面存在，則選擇最長時(shí)間不需要訪問的頁面。于所選擇的被淘汰頁面將是以后永不使用的，或者是在最長時(shí)間內(nèi)不再被訪問的頁面，這樣可以保證獲得最低的缺頁率。
2.先進(jìn)先出置換算法
是最簡單的頁面置換算法。這種算法的基本思想是：當(dāng)需要淘汰一個(gè)頁面時(shí)，總是選擇駐留主存時(shí)間最長的頁面進(jìn)行淘汰，即先進(jìn)入主存的頁面先淘汰。其理由是：最早調(diào)入主存的頁面不再被使用的可能性最大。
3.最近最久未使用置換算法
這種算法的基本思想是：利用局部性原理，根據(jù)一個(gè)作業(yè)在執(zhí)行過程中過去的頁面訪問歷史來推測未來的行為。它認(rèn)為過去一段時(shí)間里不曾被訪問過的頁面，在最近的將來可能也不會(huì)再被訪問。所以，這種算法的實(shí)質(zhì)是：當(dāng)需要淘汰一個(gè)頁面時(shí)，總是選擇在最近一段時(shí)間內(nèi)最久不用的頁面予以淘汰。
4.頁面緩沖置換算法
設(shè)立空閑頁面鏈表和已修改頁面鏈表采用可變分配和基于先進(jìn)先出的局部置換策略，并規(guī)定被淘汰頁先不做物理移動(dòng)，而是依據(jù)是否修改分別掛到空閑頁面鏈表或已修改頁面鏈表的末尾,空閑頁面鏈表同時(shí)用于物理塊分配,當(dāng)已修改頁面鏈表達(dá)到一定長度如Z個(gè)頁面時(shí)，一起將所有已修改頁面寫回磁盤，故可顯著減少磁盤I/O操作次數(shù)。
5.改進(jìn)Clock算法
改進(jìn)型Clock置換算法的主要思想是，在每次頁面替換時(shí)，總是盡可能地先替換掉既未被訪問又未被修改的頁面。
在將一個(gè)頁面換出時(shí)，如果該頁已被修改過，便須將該頁重新寫回到磁盤上；但如果該頁未被修改過，則不必將它拷回磁盤。在改進(jìn)型Clock算法中，除須考慮頁面的使用情況外，還須在增加一個(gè)因素，即置換代價(jià)，這樣頁面換出時(shí)，既要是未使用過的頁面，又要是未被修改過的頁面。把同時(shí)滿足這兩個(gè)條件的頁面作為首選淘汰的頁面。由訪問位A和修改位M可以組合成下面四種類型的頁面:
- 1類（A=0，M=0）：表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁。
- 2類（A=0，M=0）：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。
- 3類（A=1，M=0）：表示該頁最近已被訪問，但未被修改，該頁有可能在被訪問。
- 類（A=1，M=1）：表示該頁最近已被訪問且被修改，該頁可能再被訪問。
三、課題要求細(xì)化說明
- 頁表用整數(shù)數(shù)組或結(jié)構(gòu)數(shù)組來表示。
- 頁面訪問序列串是一個(gè)整數(shù)序列，整數(shù)的取值范圍為0到N - 1。頁面訪問序列串中的每個(gè)元素p表示對頁面p的一次訪問。
- 符合局部訪問特性的隨機(jī)生成算法。
- 確定虛擬內(nèi)存的尺寸N，工作集的起始位置p，工作集中包含的頁數(shù)e，工作集移動(dòng)率m（每處理m個(gè)頁面訪問則將起始位置p +1），以及一個(gè)范圍在0和1之間的值t；
- 生成m個(gè)取值范圍在p和p + e間的隨機(jī)數(shù)，并記錄到頁面訪問序列串中；
- 生成一個(gè)隨機(jī)數(shù)r，0 ≤ r ≤ 1；
- 如果r < t，則為p生成一個(gè)新值，否則p = (p + 1) mod N；
- 如果想繼續(xù)加大頁面訪問序列串的長度，請返回第2步，否則結(jié)束。
四、相關(guān)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)
根據(jù)各個(gè)算法的特點(diǎn)，程序?qū)崿F(xiàn)的過程中用到的數(shù)據(jù)結(jié)構(gòu)主要有以下兩種
- 數(shù)組：定義的時(shí)候利用指針定義，然后根據(jù)全局變量block設(shè)定的給進(jìn)程分配的物理內(nèi)存的塊數(shù)動(dòng)態(tài)分配內(nèi)存。一旦完成內(nèi)存分配，不再改變數(shù)組的大小。
用到數(shù)組結(jié)構(gòu)來實(shí)現(xiàn)的算法程序有：最佳置換算法，先進(jìn)先出置換算法，最近最久未使用置換算法，改進(jìn)型置換算法。 - 隊(duì)列：為單向隊(duì)列，隊(duì)列長度仍然由全局變量指定。
用到隊(duì)列的算法程序有：先進(jìn)先出置換算法。隊(duì)列結(jié)點(diǎn)元素的結(jié)構(gòu)體如下：
typedef struct node
{
int num;//頁號
node* next;//下一個(gè)結(jié)點(diǎn)頁面
} Node, *pNode;
typedef struct queue
{
int n;//總的結(jié)點(diǎn)數(shù)
pNode front;//隊(duì)首指針
pNode rear; //隊(duì)尾指針
} Queue, *pQueue;
- 鏈表：主要是將裝入內(nèi)存的頁塊串聯(lián)起來。
用到鏈表的算法程序：頁面緩沖算法。鏈表結(jié)點(diǎn)元素的結(jié)構(gòu)體如下:
struct LNode
{
int data;//頁號
int flag;//訪問位
int modify;//修改位
LNode* next;
};
struct Link
{
int num;//當(dāng)前鏈表上的結(jié)點(diǎn)數(shù)
LNode* next;
};
五、主要函數(shù)功能說明
1.最佳置換算法
int block = 3;
int access[32]; //訪問序列
int* memo;
int lost = 0;//沒找到的頁面數(shù)
int index = 0;//指示當(dāng)前下標(biāo)
在程序最開始定義了一些全局變量，包括物理塊的個(gè)數(shù)、訪問序列數(shù)組、內(nèi)存指針、缺頁數(shù)目等。
void generate()
{
int maxLength, e, m, p;
double t;
printf("請輸入要隨機(jī)生成訪問序列的長度\n");
scanf("%d", &maxLength);
printf("請輸入頁面數(shù)\n");
scanf("%d", &e);
printf("請輸入工作集起始位置\n");
scanf("%d", &p);
printf("請輸入工作集移動(dòng)效率\n");
scanf("%d", &m);
printf("請輸入0-1之間的t\n");
scanf("%lf", &t);
srand((unsigned)time(NULL));
int iterNum = 0;
int index=0;
for (int i = 0; i < maxLength;)
{
if (i + m >= maxLength)
iterNum = maxLength - i;
else
iterNum = m;
for (int j =0;j<iterNum;j++)
{
int temp=randomInt(p%32,(p+e)%32);
access[index]=temp;
printf("%d ",access[index]);
index++;
}
double r=randomInt(0,100)/100.0;
if(r<t)
p=randomInt(0,32);
else
p++;
i=i+iterNum;
}
printf("\n");
}
在這個(gè)void generate()函數(shù)中，按照第三節(jié)的內(nèi)容進(jìn)行了函數(shù)的構(gòu)造。
符合局部訪問特性的隨機(jī)生成算法。
- 確定虛擬內(nèi)存的尺寸N，工作集的起始位置p，工作集中包含的頁數(shù)e，工作集移動(dòng)率m（每處理m個(gè)頁面訪問則將起始位置p +1），以及一個(gè)范圍在0和1之間的值t；
- 生成m個(gè)取值范圍在p和p + e間的隨機(jī)數(shù)，并記錄到頁面訪問序列串中；
- 生成一個(gè)隨機(jī)數(shù)r，0 ≤ r ≤ 1；
- 如果r < t，則為p生成一個(gè)新值，否則p = (p + 1) mod N；
- 如果想繼續(xù)加大頁面訪問序列串的長度，請返回第2步，否則結(jié)束。
void initMemo()
{
memo = (int*) malloc (block * sizeof (int));
int i = 0;
for (; i < block; i++)
{
memo[i] = -1;
}
return;
}
在void initMemo()這個(gè)函數(shù)中，對內(nèi)存指針進(jìn)行了內(nèi)存分配與初始化。
int isInMemo (int n)
{
int i = 0;
for (; i < block; i++)
{
if (access[n] == memo[i])
{
return 1;
}
}
return 0;
}
在int isInMemo (int n)中，查詢指定頁號是否已經(jīng)在內(nèi)存中。
void optimal (int n)
{
int i = 0, j = 0;
if (isInMemo (n))
{
printf ("----------------------以下頁面已被調(diào)入,無置換----------------------\n");
}
else
if (index == block)
{
lost++;
int max = 0, pos, tag;
for (i = 0; i < block; i++)
{
tag = -1;
for (j = n + 1; j < 32; j++)
{
if (access[j] == memo[i])
{
tag = j;
break;
}
}
if (tag == -1)
{
max = 32;
pos = i;
break;
}
else
{
if (max < tag)
{
max = tag;
pos = i;
}
}
}
memo[pos] = access[n];
}
else
{
memo[index] = access[n];
index++;
}
}
void optimal (int n)是訪問一個(gè)頁面，執(zhí)行一次最佳置換算法的主函數(shù)，
void testOptimal()
{
initMemo();
int i = 0;
printf ("最佳置換算法：\n");
for (; i < 32; i++)
{
optimal (i);
printf ("%d %d %d\n", memo[0], memo[1], memo[2]);
}
printf ("最佳置換算法缺頁率： %2f \n缺頁數(shù)為： %d\n", lost / 32.0, lost);
lost = 0;
free (memo);
index = 0;
}
void testOptimal()對算法進(jìn)行了封裝與實(shí)現(xiàn)，是測試使用的主函數(shù)。
int main()
{
initMemo();
generate();
testOptimal();
printf("\n");
system("pause");
return 0;
}
定義了程序入口。
2.先進(jìn)先出置換算法
int access[32];//訪問序列
int size = 3;//給進(jìn)程分配的內(nèi)存的大小
int lost = 0;//缺頁數(shù)
在程序最開始定義了一些全局變量，包括物理塊的個(gè)數(shù)、訪問序列數(shù)組、缺頁數(shù)目等。
void generate()
{
int maxLength, e, m, p;
double t;
printf("請輸入要隨機(jī)生成訪問序列的長度\n");
scanf("%d", &maxLength);
printf("請輸入頁面數(shù)\n");
scanf("%d", &e);
printf("請輸入工作集起始位置\n");
scanf("%d", &p);
printf("請輸入工作集移動(dòng)效率\n");
scanf("%d", &m);
printf("請輸入0-1之間的t\n");
scanf("%lf", &t);
srand((unsigned)time(NULL));
int iterNum = 0;
int index=0;
for (int i = 0; i < maxLength;)
{
if (i + m >= maxLength)
iterNum = maxLength - i;
else
iterNum = m;
for (int j =0;j<iterNum;j++)
{
int temp=randomInt(p%32,(p+e)%32);
access[index]=temp;
printf("%d ",access[index]);
index++;
}
double r=randomInt(0,100)/100.0;
if(r<t)
p=randomInt(0,32);
else
p++;
i=i+iterNum;
}
printf("\n");
}
void generate()同上小節(jié)。
typedef struct node
{
int num;
struct node* next;
} Node, *pNode;
typedef struct queue
{
int n;
pNode front;
pNode rear;
} Queue, *pQueue;
定義了兩種數(shù)據(jù)結(jié)構(gòu)體。
void initQueue (pQueue q)
{
q->rear = (pNode) malloc (sizeof (Node));
if (q->rear == NULL)
{
printf ("failed\n");
}
else
{
q->front = q->rear;
q->rear->next = NULL;
q->front->next = NULL;
q->n = 0;
}
}
void initQueue (pQueue q)初始化隊(duì)列。
void push (pQueue q, int num)
{
pNode p = (pNode) malloc (sizeof (Node));
if (p == NULL)
{
printf ("failed");
}
else
{
p->next = NULL;
p->num = num;
if (q->front == q->rear)
{
q->front->next = p;
q->rear = p;
}
else
{
q->rear->next = p;
q->rear = p;
}
q->n++;
}
}
void push (pQueue q, int num)是在隊(duì)列中加入新的頁面結(jié)點(diǎn)。
void pop (pQueue q)
{
pNode p;
if (q->front != q->rear)
{
p = q->front->next;
q->front->next = p->next;
if (p == q->rear)
{
q->front = q->rear;
}
q->n--;
free (p);
}
}
void pop (pQueue q)將頁面移出內(nèi)存。
void destroy (pQueue q)
{
while (q->front != q->rear)
{
pop (q);
}
}
void destroy (pQueue q)銷毀隊(duì)列釋放內(nèi)存。
int findInQueue (pQueue q, int num)
{
pNode p;
if (q->front != q->rear)
{
p = q->front->next;
while (p)
{
if (p->num == num)
{
return 1;
}
else
{
p = p->next;
}
}
}
return 0;
}
int findInQueue (pQueue q, int num)查找頁面是否已經(jīng)調(diào)入內(nèi)存。
void fifo (pQueue q, int num)
{
if (findInQueue (q, num))
{
printf ("----------------------以下頁面已被調(diào)入,無置換----------------------\n");
}
else
{
if (q->n == size)
{
pop (q);
push (q, num);
lost++;
}
else
{
push (q, num);
}
}
}
void fifo (pQueue q, int num)每訪問一個(gè)頁面，執(zhí)行一次算法。
void fifoTest()
{
Queue q;
pNode p;
initQueue (&q);
int i = 0;
printf ("先進(jìn)先出置換算法\n");
for (; i < 32; i++)
{
fifo (&q, access[i]);
p = q.front->next;
while (p)
{
printf ("%d ", p->num);
p = p->next;
}
printf ("\n");
}
printf ("先進(jìn)先出算法缺頁率：%2f \n缺頁數(shù)為： %d\n", lost / 32.0, lost);
destroy (&q);
}
void fifoTest()先進(jìn)先出置換算法實(shí)現(xiàn)函數(shù)。
int main()
{
generate();
fifoTest();
return 0;
}
程序入口。
3.最近最久未使用置換算法
int block = 3;
int access[32]; //訪問序列
int* memo;
int lost = 0;//沒找到的頁面數(shù)
int index = 0;//指示當(dāng)前下標(biāo)
設(shè)置全局變量。
void generate()
{
int maxLength, e, m, p;
double t;
printf("請輸入要隨機(jī)生成訪問序列的長度\n");
scanf("%d", &maxLength);
printf("請輸入頁面數(shù)\n");
scanf("%d", &e);
printf("請輸入工作集起始位置\n");
scanf("%d", &p);
printf("請輸入工作集移動(dòng)效率\n");
scanf("%d", &m);
printf("請輸入0-1之間的t\n");
scanf("%lf", &t);
srand((unsigned)time(NULL));
int iterNum = 0;
int index=0;
for (int i = 0; i < maxLength;)
{
if (i + m >= maxLength)
iterNum = maxLength - i;
else
iterNum = m;
for (int j =0;j<iterNum;j++)
{
int temp=randomInt(p%32,(p+e)%32);
access[index]=temp;
printf("%d ",access[index]);
index++;
}
double r=randomInt(0,100)/100.0;
if(r<t)
p=randomInt(0,32);
else
p++;
i=i+iterNum;
}
printf("\n");
}
同上。
void initMemo()
{
memo = (int*) malloc (block * sizeof (int));
int i = 0;
for (; i < block; i++)
{
memo[i] = -1;
}
return;
}
初始化內(nèi)存。
int isInMemo (int n)
{
int i = 0;
for (; i < block; i++)
{
if (access[n] == memo[i])
{
return 1;
}
}
return 0;
}
判斷是否在內(nèi)存中。
void LRU (int n)
{
int i, j;
if (isInMemo (n))
{
printf ("----------------------以下頁面已被調(diào)入,無置換----------------------\n");
}
else
if (index == block)
{
int max = n, pos = -1, tag;
for (i = 0; i < block; i++)
{
for (j = n - 1; j >= 0; j--)
{
if (access[j] == memo[i])
{
tag = j;
break;
}
}
if (tag < max)
{
max = tag;
pos = i;
if (max == 0)
{
break;
}
}
}
memo[pos] = access[n];
lost++;
}
else
{
memo[index] = access[n];
index++;
}
}
LRU算法主函數(shù)，每執(zhí)行一次查詢置換一頁。
void testLRU()
{
int i;
initMemo();
printf ("最近最久未使用算法\n");
for (i = 0; i < 32; i++)
{
LRU (i);
printf ("%d %d %d\n", memo[0], memo[1], memo[2]);
}
printf ("最近最久未使用缺頁率： %2f \n缺頁數(shù)為： %d\n", lost / 32.0, lost);
lost = 0;
index = 0;
free (memo);
}
封裝函數(shù)。
int main()
{
initMemo();
generate();
testLRU();
printf("\n");
system("pause");
return 0;
}
程序入口。
4.改進(jìn)型Clock置換算法
typedef struct Lnode
{
int data;
int flag;//訪問位
int modify;//修改位
} LNode;
設(shè)置對應(yīng)結(jié)構(gòu)體。
int block = 3;
int access[32]; //訪問序列
int lost = 0,index=0;//沒找到的頁面數(shù)
LNode* nodes;//改進(jìn)型Clock置換算法用到的數(shù)據(jù)結(jié)構(gòu)
初始化全局變量。
void generate()
{
int maxLength, e, m, p;
double t;
printf("請輸入要隨機(jī)生成訪問序列的長度\n");
scanf("%d", &maxLength);
printf("請輸入頁面數(shù)\n");
scanf("%d", &e);
printf("請輸入工作集起始位置\n");
scanf("%d", &p);
printf("請輸入工作集移動(dòng)效率\n");
scanf("%d", &m);
printf("請輸入0-1之間的t\n");
scanf("%lf", &t);
srand((unsigned)time(NULL));
int iterNum = 0;
int index=0;
for (int i = 0; i < maxLength;)
{
if (i + m >= maxLength)
iterNum = maxLength - i;
else
iterNum = m;
for (int j =0;j<iterNum;j++)
{
int temp=randomInt(p%32,(p+e)%32);
access[index]=temp;
printf("%d ",access[index]);
index++;
}
double r=randomInt(0,100)/100.0;
if(r<t)
p=randomInt(0,32);
else
p++;
i=i+iterNum;
}
printf("\n");
}
同上。
int isInNodes (int n)
{
int i;
for (i = 0; i < block; i++)
{
if (nodes[i].data == access[n])
{
return 1;
}
}
return 0;
}
頁面是否已經(jīng)在鏈表中
void updated_Clock (int n)
{
if (isInNodes (n))
{
printf ("----------------------以下頁面已被調(diào)入,無置換----------------------\n");
}
else
if (index == block)
{
lost++;
int i = 0, tag = -1;
while (1)
{
if ( (i / block) % 2 == 0)
{
if (nodes[i % block].flag == 0 && nodes[i % block].modify == 0)
{
tag = i % block;
break;
}
}
if ( (i / block) % 2 == 1)
{
if (nodes[i % block].flag == 0 && nodes[i % block].modify == 1)
{
tag = i % block;
break;
}
else
{
nodes[i % block].flag = 0;
}
}
i++;
}
nodes[tag].data = access[n];
nodes[tag].flag = 1;
if (rand() % 10 < 4)
{
nodes[tag].modify = 1;
}
else
{
nodes[tag].modify = 0;
}
}
else
{
nodes[index].data = access[n];
nodes[index].flag = 1;
if (rand() % 10 < 4)
{
nodes[index].modify = 1;
}
else
{
nodes[index].modify = 0;
}
index++;
}
}
每訪問一個(gè)新的頁面，執(zhí)行一次算法。
void test_Clock()
{
int i = 0, j = 0;
printf ("改進(jìn)型Clock置換算法\n");
nodes = (LNode*) malloc (block * sizeof (LNode));
for (i = 0; i < block; i++)
{
nodes[i].data = -1;
nodes[i].flag = -1;
nodes[i].modify = -1;
}
for (i = 0; i < 32; i++)
{
updated_Clock (i);
for (j = 0; j < block; j++)
{
printf ("%d ", nodes[j].data);
}
printf ("\n");
}
printf ("改進(jìn)型Clock置換算法缺頁率： %2f \n缺頁數(shù)為： %d\n", lost / 32.0, lost);
lost = 0;
index = 0;
}
改進(jìn)型clock算法實(shí)現(xiàn)函數(shù)。
int main()
{
generate();
test_Clock();
}
程序入口。
5.頁面緩沖算法
typedef struct Lnode
{
int data;
int flag;//訪問位
int modify;//修改位
struct LNode* next;
}LNode;
typedef struct Link
{
int num;//當(dāng)前鏈表上的結(jié)點(diǎn)數(shù)
LNode* next;
}Link;
建立鏈表結(jié)構(gòu)體。
int size = 3;
int p;//工作集的起始位置
int table[32];//物理內(nèi)存，每一個(gè)元素代表一個(gè)頁面
int access[32]; //訪問序列
int memo[3] = { -1, -1, -1 };
int lost = 0;//沒找到的頁面數(shù)
int index = 0;//指示當(dāng)前下標(biāo)
LNode* nodes;//PBA用到的數(shù)據(jù)結(jié)構(gòu)
Link idle;
Link modified;
初始化全局變量。
void generate()
{
int maxLength, e, m, p;
double t;
printf("請輸入要隨機(jī)生成訪問序列的長度\n");
scanf("%d", &maxLength);
printf("請輸入頁面數(shù)\n");
scanf("%d", &e);
printf("請輸入工作集起始位置\n");
scanf("%d", &p);
printf("請輸入工作集移動(dòng)效率\n");
scanf("%d", &m);
printf("請輸入0-1之間的t\n");
scanf("%lf", &t);
srand((unsigned)time(NULL));
int iterNum = 0;
int index=0;
for (int i = 0; i < maxLength;)
{
if (i + m >= maxLength)
iterNum = maxLength - i;
else
iterNum = m;
for (int j =0;j<iterNum;j++)
{
int temp=randomInt(p%32,(p+e)%32);
access[index]=temp;
printf("%d ",access[index]);
index++;
}
double r=randomInt(0,100)/100.0;
if(r<t)
p=randomInt(0,32);
else
p++;
i=i+iterNum;
}
printf("\n");
}
同上。
int isInNodes (int n)
{
int i;
for (i = 0; i < 3; i++)
{
if (nodes[i].data == access[n])
{
return 1;
}
}
return 0;
}
頁面是否已經(jīng)在鏈表中。
LNode* isinLinks (int n)
{
LNode*p, *q;
p = idle.next;
q = NULL;
while (p)
{
if (p->data == access[n])
{
if (q != NULL)
{
q->next = p->next;
p->next = NULL;
idle.num--;
break;
}
else
{
idle.next = NULL;
}
}
q = p;
p = p->next;
}
if (p == NULL)
{
p = modified.next;
while (p != NULL)
{
if (p->data == access[n])
{
if (p == modified.next)
{ modified.next = p->next; }
else
{
q->next = p->next;
p->next = NULL;
modified.num--;
}
if (modified.num == 0)
{ modified.next = NULL; }
break;
}
q = p;
p = p->next;
}
}
return p;
}
void PBA (int n)
{
if (isInNodes (n))
{
printf ("已裝入內(nèi)存\n");
}
else
if (index == size)
{
LNode *p;
if ( (p = isinLinks (n)) != NULL)
{
nodes = (LNode*) realloc (nodes, (size + 1) * sizeof (LNode));
nodes[size] .data = p->data;
nodes[size].flag = p->flag;
nodes[size].modify = p->modify;
nodes[size].next = p->next;
free (p);
size++;
index++;
}
else
{
lost++;//缺頁
if (nodes[n % 3].modify == 1)
{
addToLink (nodes[n % 3].data, 1);
}
else
{
addToLink (nodes[n % 3].data, 0);
}
nodes[n % 3].data = access[n];
nodes[n % 3].flag = 1;
nodes[n % 3].next = NULL;
if (rand() % 10 < 4)
{
nodes[n % 3].modify = 0;
}
else
{
nodes[n % 3].modify = 1;
}
}
}
else
{
nodes[index].data = access[n];
nodes[index].flag = 1;
nodes[index].next = NULL;
if (rand() % 10 < 4)
{
nodes[index].modify = 1;
}
else
{
nodes[index].modify = 0;
}
index++;
}
}
PBA算法實(shí)現(xiàn)函數(shù)。
void addToLink (int data, int type)
{
LNode* p;
LNode* q;
q = (LNode*) malloc (sizeof (LNode));
q->data = data;
q->flag = 1;
if (type == 1)
{
q->modify = 1;
p = modified.next;
}
else
{
q->modify = 0;
p = idle.next;
}
q->next = NULL;
if (p == NULL)
{
if (type == 0)
{
idle.next = q;
}
else
{
modified.next = q;
}
}
else
{
while (p)
{
if (p->next == NULL)
{
p->next = q;
break;
}
else
{
p = p->next;
}
}
}
if (type == 0)
{
idle.num += 1;
if (idle.num == 10)
{
emptyIdle();
}
}
else
{
modified.num += 1;
if (modified.num == 10)
{
emptyModi();
}
}
}
頁面添加到已修改頁面鏈表和空閑鏈表上。
void emptyIdle ()
{
LNode* p;
p = idle.next;
while (p)
{
idle.next = p->next;
free (p);
p = idle.next;
}
idle.num = 0;
}
將空閑鏈表上的所有頁面送出內(nèi)存。
void emptyModi()
{
LNode* p;
p = modified.next;
while (p)
{
modified.next = p->next;
free (p);
p = modified.next;
}
modified.num = 0;
}
將已修改頁面鏈表上所有的鏈表送出內(nèi)存。
int main()
{
int i = 0, j = 0;
generate();
printf ("頁面緩沖置換算法(PBA)\n");
idle.num = 0;
idle.next = NULL;
modified.num = 0;
modified.next = NULL;
nodes = (LNode*) malloc (size * sizeof (LNode));
for (i = 0; i < size; i++)
{
nodes[i].data = -1;
nodes[i].flag = 0;
nodes[i].modify = 0;
nodes[i].next = NULL;
}
for (i = 0; i < 32; i++)
{
PBA (i);
for (j = 0; j < size; j++)
{
printf ("%d ", nodes[j].data);
}
printf ("\n");
}
printf ("頁面緩沖置換算法（PBA）缺頁率：%f %d\n", lost / 32.0, lost);
system("pause");
return 0;
}
程序入口。
六、程序執(zhí)行結(jié)果
1.最佳置換算法
可以看到，一共32個(gè)頁面，有18個(gè)缺頁，缺頁率為0.563。
2.先進(jìn)先出算法
可以看到，一共32個(gè)頁面，有19個(gè)缺頁，缺頁率為0.594。
3.最近最久未使用置換算法
可以看到，一共32個(gè)頁面，有18個(gè)缺頁，缺頁率為0.563。
4.改進(jìn)型clock置換算法
可以看到，一共32個(gè)頁面，有20個(gè)缺頁，缺頁率為0.625。
5.頁面緩沖置換算法
可以看到，一共32個(gè)頁面，有18個(gè)缺頁，缺頁率為0.563。
七、測試與分析
利用genenrate()函數(shù)生成3個(gè)訪問序列，記錄每個(gè)序列下，每種算法的缺頁情況，最終整理得到如下統(tǒng)計(jì)表格：
訪問序列的長度始終為32，默認(rèn)初始分配給每種算法的內(nèi)存空間塊數(shù)為3。
| 置換算法 | 最佳置換算法 | 先進(jìn)先出置換算法 | 最近最久未使用算法 | 改進(jìn)型clock置換算法 | 頁面緩沖置換算法 |
|---|---|---|---|---|---|
| 測試序列1缺頁數(shù) | 13 | 17 | 20 | 15 | 18 |
| 測試序列1缺頁數(shù) | 11 | 12 | 15 | 21 | 14 |
| 測試序列1缺頁數(shù) | 14 | 16 | 16 | 16 | 14 |
使用同樣的訪問序列，改變分配給每種算法的的內(nèi)存空間塊數(shù)為5，得到實(shí)驗(yàn)結(jié)果如下:
| 置換算法 | 最佳置換算法 | 先進(jìn)先出置換算法 | 最近最久未使用算法 | 改進(jìn)型clock置換算法 | 頁面緩沖置換算法 |
|---|---|---|---|---|---|
| 測試序列1缺頁數(shù) | 8 | 12 | 13 | 14 | 16 |
| 測試序列1缺頁數(shù) | 7 | 9 | 11 | 15 | 10 |
| 測試序列1缺頁數(shù) | 9 | 9 | 11 | 13 | 10 |
重新生成1000組序列，求缺頁率平均值，可以做出以下圖像：
從以上數(shù)據(jù)觀察我們可以得到如下結(jié)論：
（1）同一種算法，對于不同的訪問序列，其缺頁率是不同，會(huì)有所變化。
（2）總的來看，最佳置換算法的缺頁率是最低的，這一點(diǎn)是毋庸置疑的。剩下的集中算法中，頁面緩沖算法的缺頁率要低于其他置換算法。改進(jìn)型clock算法稍微好于先進(jìn)先出算法和最近最久未使用算法。先進(jìn)先出算法和最近最久未使用算法性能相近?？偟膩砜?，性能（缺頁率）如下。
最佳置換算法>頁面緩沖置換算法>改進(jìn)型clock置換算法>最近最久未使用算法>=先進(jìn)先出置換算法。
（3）對比內(nèi)存塊數(shù)為3和內(nèi)存塊數(shù)為5兩種情況下的同一序列下的情況，可以發(fā)現(xiàn)，算法的缺頁率還跟分配的內(nèi)存塊數(shù)有關(guān)系，分配的內(nèi)存塊數(shù)越多，缺頁率越低。這與直觀感受是一致的，即導(dǎo)入內(nèi)存的塊數(shù)越多，發(fā)生缺頁的可能性就越小。
八、總結(jié)
在這里對常見的三種算法做一個(gè)對比和總結(jié)：
- 先入先出法（FIFO）
最簡單的頁面置換算法是先入先出（FIFO）法。這種算法的實(shí)質(zhì)是，總是選擇在主存中停留時(shí)間最長（即最老）的一頁置換，即先進(jìn)入內(nèi)存的頁，先退出內(nèi)存。理由是：最早調(diào)入內(nèi)存的頁，其不再被使用的可能性比剛調(diào)入內(nèi)存的可能性大。建立一個(gè)FIFO隊(duì)列，收容所有在內(nèi)存中的頁。被置換頁面總是在隊(duì)列頭上進(jìn)行。當(dāng)一個(gè)頁面被放入內(nèi)存時(shí)，就把它插在隊(duì)尾上。
這種算法只是在按線性順序訪問地址空間時(shí)才是理想的，否則效率不高。因?yàn)槟切┏１辉L問的頁，往往在主存中也停留得最久，結(jié)果它們因變“老”而不得不被置換出去。
FIFO的另一個(gè)缺點(diǎn)是，它有一種異?，F(xiàn)象，即在增加存儲(chǔ)塊的情況下，反而使缺頁中斷率增加了。當(dāng)然，導(dǎo)致這種異?，F(xiàn)象的頁面走向?qū)嶋H上是很少見的。 - 最優(yōu)置換算法（OPT）
最優(yōu)置換（Optimal Replacement）是在理論上提出的一種算法。其實(shí)質(zhì)是：當(dāng)調(diào)入新的一頁而必須預(yù)先置換某個(gè)老頁時(shí)，所選擇的老頁應(yīng)是將來不再被使用，或者是在最遠(yuǎn)的將來才被訪問。采用這種頁面置換算法，保證有最少的缺頁率。
但是最優(yōu)頁面置換算法的實(shí)現(xiàn)是困難的，因?yàn)樗枰藗冾A(yù)先就知道一個(gè)進(jìn)程整個(gè)運(yùn)行過程中頁面走向的全部情況。不過，這個(gè)算法可用來衡量（如通過模擬實(shí)驗(yàn)分析或理論分析）其他算法的優(yōu)劣。 - 最久未使用算法（LRU）
FIFO算法和OPT算法之間的主要差別是，F(xiàn)IFO算法利用頁面進(jìn)入內(nèi)存后的時(shí)間長短作為置換依據(jù)，而OPT算法的依據(jù)是將來使用頁面的時(shí)間。如果以最近的過去作為不久將來的近似，那么就可以把過去最長一段時(shí)間里不曾被使用的頁面置換掉。它的實(shí)質(zhì)是，當(dāng)需要置換一頁時(shí)，選擇在最近一段時(shí)間里最久沒有使用過的頁面予以置換。這種算法就稱為最久未使用算法（Least Recently Used，LRU）。
LRU算法是與每個(gè)頁面最后使用的時(shí)間有關(guān)的。當(dāng)必須置換一個(gè)頁面時(shí)，LRU算法選擇過去一段時(shí)間里最久未被使用的頁面。
LRU算法是經(jīng)常采用的頁面置換算法，并被認(rèn)為是相當(dāng)好的，但是存在如何實(shí)現(xiàn)它的問題。LRU算法需要實(shí)際硬件的支持。其問題是怎么確定最后使用時(shí)間的順序，對此有兩種可行的辦法：
（1）計(jì)數(shù)器。最簡單的情況是使每個(gè)頁表項(xiàng)對應(yīng)一個(gè)使用時(shí)間字段，并給CPU增加一個(gè)邏輯時(shí)鐘或計(jì)數(shù)器。每次存儲(chǔ)訪問，該時(shí)鐘都加1。每當(dāng)訪問一個(gè)頁面時(shí)，時(shí)鐘寄存器的內(nèi)容就被復(fù)制到相應(yīng)頁表項(xiàng)的使用時(shí)間字段中。這樣我們就可以始終保留著每個(gè)頁面最后訪問的“時(shí)間”。在置換頁面時(shí)，選擇該時(shí)間值最小的頁面。這樣做，不僅要查頁表，而且當(dāng)頁表改變時(shí)（因CPU調(diào)度）要維護(hù)這個(gè)頁表中的時(shí)間，還要考慮到時(shí)鐘值溢出的問題。
（2）棧。用一個(gè)棧保留頁號。每當(dāng)訪問一個(gè)頁面時(shí)，就把它從棧中取出放在棧頂上。這樣一來，棧頂總是放有目前使用最多的頁，而棧底放著目前最少使用的頁。由于要從棧的中間移走一項(xiàng)，所以要用具有頭尾指針的雙向鏈連起來。在最壞的情況下，移走一頁并把它放在棧頂上需要改動(dòng)6個(gè)指針。每次修改都要有開銷，但需要置換哪個(gè)頁面卻可直接得到，用不著查找，因?yàn)槲仓羔樦赶驐５?，其中有被置換頁。
因?qū)崿F(xiàn)LRU算法必須有大量硬件支持，還需要一定的軟件開銷。所以實(shí)際實(shí)現(xiàn)的都是一種簡單有效的LRU近似算法。
LRU和FIFO本質(zhì)都是先進(jìn)先出的思路，但LRU是針對頁面的最近訪問時(shí)間來進(jìn)行排序，所以需要在每一次頁面訪問的時(shí)候動(dòng)態(tài)的調(diào)整各個(gè)頁面之間的先后順序（每一個(gè)頁面的最近訪問時(shí)間變了）；而FIFO針對頁面進(jìn)入內(nèi)存的時(shí)間來進(jìn)行排序，這個(gè)時(shí)間是固定不變的，所以頁面之間的先后順序是固定不變的。如果程序局部性，則LRU會(huì)很好。如果內(nèi)存中所有頁面都沒有被訪問過會(huì)退化為FIFO（如頁面進(jìn)入內(nèi)存后沒有被訪問，最近訪問時(shí)間與進(jìn)入內(nèi)存的時(shí)間相同）。
LRU算法性能較好，但系統(tǒng)開銷較大；FIFO算法的系統(tǒng)的開銷較小，但可能發(fā)生Belady現(xiàn)象。因此，擇衷的辦法就是Clock算法，在每一次頁面訪問時(shí)，它不必去動(dòng)態(tài)調(diào)整頁面在鏈表中的順序，而僅僅是做一個(gè)標(biāo)記，等待發(fā)生缺頁中斷的時(shí)候，再把它移動(dòng)到鏈表的末尾。對于內(nèi)存當(dāng)中未被訪問的頁面，Clock算法的表現(xiàn)與LRU一樣好，而對于那些曾經(jīng)訪問過的頁面，它不能像LRU那樣記住它們的準(zhǔn)確訪問順序。
代碼鏈接：Github
