文章目錄
一、概述
?（1）置換算法
?（2）缺頁率與命中率
二、先進先出置換算法（FIFO）
?? (1)定義
?? (2)示例
?（3）Belady異常
?三、最近最久未使用置換算法（LRU）
（1）定義
（2）示例
四、FIFO&LRU置換算法的模擬
?? (1)流程圖
?（2）完整代碼
?（3）實驗結果
一、概述
（1）置換算法
????????進程運行時，若其訪問的頁面不在內存中而需要將其調入，但內存已經(jīng)無空閑空間時，就需要從內存中調出一頁程序或者數(shù)據(jù)，送入磁盤的對換區(qū)。
????????選擇調出頁面的算法就稱為頁面置換算法。常見的頁面置換算法有以下四種：
- 最佳置換算法（OPT）
- 先進先出頁面置換算法（FIFO）
- 最近最久未使用置換算法（LRU）
- 時鐘置換算法（CLOCL）
（2）缺頁率與命中率
????????當前訪問的頁面不在內存中時，此時發(fā)生缺頁中斷，選擇合適的頁面置換算法來從內存中調出一頁程序或者數(shù)據(jù)，送入磁盤的對換區(qū)，與當前要訪問的頁面進行置換，從而滿足當前的訪問需求。這種情況就叫缺頁，相反，如果當前訪問的頁面在內存中時，即為命中。二者有如下關系：
- 缺頁率+命中率=1
- 缺頁率=缺頁次數(shù)/總頁面訪問次數(shù)
- 命中率=命中次數(shù)/總頁面訪問次數(shù)
本次實驗重點是模擬先進先出和最近最久未使用算法的執(zhí)行過程。
二、先進先出置換算法（FIFO）
(1)定義
????????優(yōu)先淘汰那些最早進入內存的頁面，即淘汰在內存中駐留時間最久的頁面。該算法實現(xiàn)簡單，只需把已調入內存的頁面根據(jù)先后次序鏈接成隊列，設置一個指針總是指向最老的頁面。
(2)示例
假定系統(tǒng)為某個進程分配了3個物理塊,訪問頁面依次如下:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
按照FIFO算法， 當依次訪問頁面7,0,1時，由于都不在內存中發(fā)生缺頁中斷，因為有3個物理塊且內存空閑，所以可以不用置換頁面直接將這三個頁面依次放入內存中；當訪問頁面2時，由于不在內存中，發(fā)生缺頁中斷，此時按照FIFO置換算法將內存中最早進入內存的頁面7與2置換，讓2進入內存，后面以此類推。
（3）Belady異常
????????分配給進程的物理塊增多，但是缺頁率卻不減反增的現(xiàn)象被稱之為Belady異常。如圖：
?當進程有3個物理塊時，缺頁次數(shù)為9，缺頁率為75%
?當進程有4個物理塊時，缺頁次數(shù)為10，缺頁率為83.33%
?另外，只有FIFO算法會出現(xiàn)Belady異常，其它算法不會出現(xiàn)這種情況！
?三、最近最久未使用置換算法（LRU）
（1）定義
????????選擇最近最長時間未訪問過的頁面予以淘汰，它認為過去一段時間內未訪問過的頁面，在最近的將來可能也不會被訪問。該算法為每個頁面設置一個訪問字段，用來記錄頁面自上次被訪問以來所經(jīng)歷的時間，淘汰頁面時選擇現(xiàn)有頁面中值最大的予以淘汰。
（2）示例
????????再對上面的例子采用LRU算法進行頁面置換，如圖3.25所示。進程第一次對頁面 2訪問時，將最近最久未被訪問的頁面7置換出去。然后在訪問頁面3時，將最近最久未使用的頁面1換出。
????????LRU算法的性能較好，但需要寄存器和棧的硬件支持。LRU是堆棧類的算法。理論上可以證明，堆棧類算法不可能出現(xiàn)Belady異常。FIFO 算法基于隊列實現(xiàn)，不是堆棧類算法。
四、FIFO&LRU置換算法的模擬
(1)流程圖
?（2）完整代碼
/*
虛擬存儲器之頁面置換算法的模擬
測試數(shù)據(jù)1：20個訪問的頁面 3個物理塊:
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
測試數(shù)據(jù)2:10個訪問頁面 2個物理塊
4 2 3 0 3 2 1 2 0 1
*/
#include <stdio.h>
#define phy 100
#define page 100//頁面最大數(shù)
#define phyBlock 100//物理塊最大數(shù)
int phyBlockNum;//物理塊的數(shù)量
int pageNum;//頁面數(shù)量
int pageNumStrList[page];//保存頁面號引用串
//初始化隊列
void initializeList(int list[], int number)
{
for (int i = 0; i < number; i++)
{
list[i] = -1;
}
}
//展示當前隊列狀態(tài)
void showList(int list[], int number)
{
for (int i = 0; i < number; i++)
{
printf("%2d", list[i]);
}
printf("\n");
}
//展示當前系統(tǒng)內存狀態(tài)
void showMemoryList(int list[], int phyBlockNum)
{
for (int i = 0; i < phyBlockNum; i++)
{
if (list[i] == -1)
{
break;
}
printf(" |%d|\t", list[i]);
}
printf("\n");
}
//頁面置換結果分析統(tǒng)計
void informationCount(int missingCount, int replaceCount, int pageNum)
{
printf("---------------------------結果分析--------------------------\n");
printf("缺頁次數(shù):%d\n", missingCount);
double a=(double)missingCount/pageNum;//計算缺頁率以百分號形式表示
printf("缺頁率:%.2f%%\n", a*100);
double result = (double)(pageNum - missingCount) / (double)pageNum;
printf("置換次數(shù):%d\n", replaceCount);
printf("------------------------------------------------------------\n");
}
//尋找該頁面下次要訪問的位置
int getNextPosition(int currentPage, int currentPosition, int strList[], int pageNum)
{
for (int i = currentPosition + 1; i < pageNum; i++)
{
if (strList[i] == currentPage)
{
return i;
}
}
return 100;
}
//FIFO:先進先出置換算法
void replacePageByFIFO(int memoryList[], int phyNum, int strList[], int pageNum) {
int replaceCount = 0; //置換次數(shù)
int missingCount = 0; //缺頁次數(shù)
int pointer = 0; //記錄當前最早進入內存的下標
int isVisited = 0;//記錄當前頁面的訪問情況: 0表示未訪問，1表示已訪問
for (int i = 0; i < pageNum; i++) {
isVisited = 0;
//判斷是否需要置換，內存已滿且需要訪問的頁面不在內存中
for (int j = 0; j < phyNum; j++) {
if (memoryList[j] == strList[i]) {
//1.該頁面已經(jīng)存在內存中
//修改訪問情況
isVisited = 1;
//修改訪問時間
printf("%d\t", strList[i]);
printf("\n");
break;
}
if (memoryList[j] == -1) {
//2.頁面不在內存中且內存未滿則直接存入即可
memoryList[j] = strList[i];
//修改訪問情況
isVisited = 1;
missingCount++;
printf("%d\t", strList[i]);
showMemoryList(memoryList, phyNum);
break;
}
}
//當前頁面還未被訪問過，需要進行頁面置換
if (!isVisited) {
//直接把這個頁面存到所記錄的下標中
memoryList[pointer] = strList[i];
pointer++; //下標指向下一個
//如果到了最后一個，將下標歸零
if (pointer > phyNum - 1) {
pointer = 0;
}
missingCount++;
replaceCount++;
printf("%d\t", strList[i]);
showMemoryList(memoryList, phyNum);
}
}
informationCount(missingCount, replaceCount, pageNum);
}
//LRU:最近最久未使用置換算法
void replacePageByLRU(int memoryList[], int phyNum, int strList[], int pageNum) {
int replaceCount = 0;//置換次數(shù)
int missingCount = 0; //缺頁次數(shù)
int timeRecord[phy]; //記錄內存中最近一次訪問至今的時間
initializeList(timeRecord, phyNum);
int isVisited = 0;
//記錄已經(jīng)在內存中的頁面數(shù)量
int pageCount = 0;
for (int i = 0; i < pageNum; i++) {
isVisited = 0;
//時間加一
for (int p = 0; p < pageCount; p++) {
if (memoryList[p] != -1) {
timeRecord[p] ++;
}
}
//是否需要置換
for (int j = 0; j < phyNum; j++) {
if (memoryList[j] != -1) {
timeRecord[j] ++;
}
if (memoryList[j] == strList[i]) {
//該頁面已經(jīng)存在內存中
//修改訪問情況
isVisited = 1;
//重置訪問時間
timeRecord[j] = -1;
printf("%d\t", strList[i]);
printf("\n");
break;
}
if (memoryList[j] == -1) {
//頁面不在內存中且內存未滿，直接存入
memoryList[j] = strList[i];
pageCount++;
//修改訪問情況
isVisited = 1;
//修改訪問時間
timeRecord[j]++;
missingCount++;
printf("%d\t", strList[i]);
showMemoryList(memoryList, phyNum);
break;
}
}
//不在內存中，則需要進行頁面置換
if (!isVisited) {
//1.遍歷時間記錄表，尋找最久未訪問的頁面所在的內存下標
int max = 0;
for (int k = 0; k < phyNum; k++) {
if (timeRecord[max] < timeRecord[k]) {
max = k;
}
}
//2.將該位置的頁面換出
memoryList[max] = strList[i];
timeRecord[max] = -1;
missingCount++;
replaceCount++;
printf("%d\t", strList[i]);
showMemoryList(memoryList, phyNum);
}
}
informationCount(missingCount, replaceCount, pageNum);
}
//測試
int main(int argc, const char* argv[])
{
printf("------------------虛擬存儲器之頁面置換算法------------------\n");
printf("請輸入內存的物理塊數(shù)量:");
scanf("%d", &phyBlockNum);
//生成內存隊列
int memoryList[phyBlock];
//初始化內存狀態(tài)
initializeList(memoryList, phyBlockNum);
//showMemoryList(memoryList,phyBlockNum);
printf("請輸入要訪問的頁面總數(shù):");
scanf("%d", &pageNum);
printf("請輸入要訪問的頁面號:");
for (int i = 0; i < pageNum; i++) {
scanf("%d", &pageNumStrList[i]);
}
printf("------------------------------------------------------------\n");
int chose;
while (1)
{
printf("★請選擇你要執(zhí)行的操作：(1.FIFO算法 2.LRU算法 3.退出):");
scanf("%d", &chose);
switch (chose)
{
case 1:
printf("------------------------------------------------------------\n");
printf("頁面號\t");
for(int i=0;i<phyBlockNum;i++){
printf("物理塊%d\t",i+1);
}
printf("\n");
replacePageByFIFO(memoryList, phyBlockNum, pageNumStrList, pageNum);
//重新初始化內存
initializeList(memoryList, phyBlockNum);
break;
case 2:
printf("------------------------------------------------------------\n");
printf("頁面號\t");
for(int i=0;i<phyBlockNum;i++){
printf("物理塊%d\t",i+1);
}
printf("\n");
replacePageByLRU(memoryList, phyBlockNum, pageNumStrList, pageNum);
//重新初始化內存
initializeList(memoryList, phyBlockNum);
break;
default:
printf("退出成功");
return 0;
break;
}
}
return 0;
}
（3）實驗結果
文章來源：http://www.zghlxwxcb.cn/news/detail-445299.html
最后， 如果本文內容對你有所幫助，記得點贊收藏哈。文章來源地址http://www.zghlxwxcb.cn/news/detail-445299.html
到了這里，關于操作系統(tǒng)實驗三虛擬存儲器管理之模擬頁面置換算法（FIFO&LRU）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
